Count Prefixes of a Given String

Easy
1015.

Count Prefixes of a Given String

Count Prefixes of a Given String is an easy coding problem on arrays and strings, asked in Amazon, Google and Wipro interviews.

Return the number of strings in words that are a prefix of s.

A prefix is any leading run of characters, including the whole string.

Example 1

Input
words = ["co","code","kai","codek"], s = "codekairo"
Output
3
Explanation
`co`, `code` and `codek` all start `codekairo`; `kai` does not.

Example 2

Input
words = ["a","b","c","ab","bc","abc"], s = "abc"
Output
3
Explanation
`a`, `ab` and `abc`.

Example 3

Input
words = ["a","a"], s = "aa"
Output
2
Explanation
Duplicates each count.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length, s.length <= 10
  • words[i] and s consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} s
 * @return {number}
 */
var countPrefixes = function(words, s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Prefixes of a Given String — Problem & Solution

Count Prefixes of a Given String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Prefixes of a Given String is an easy coding problem on arrays and strings, asked in Amazon, Google and Wipro interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings
  • Asked at: Amazon, Google, Wipro
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the number of strings in words that are a prefix of s.

A prefix is any leading run of characters, including the whole string.

Example 1

Input: words = ["co","code","kai","codek"], s = "codekairo"
Output: 3
Explanation: `co`, `code` and `codek` all start `codekairo`; `kai` does not.

Example 2

Input: words = ["a","b","c","ab","bc","abc"], s = "abc"
Output: 3
Explanation: `a`, `ab` and `abc`.

Example 3

Input: words = ["a","a"], s = "aa"
Output: 2
Explanation: Duplicates each count.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length, s.length <= 10
  • words[i] and s consist of lowercase English letters.

Hints for Count Prefixes of a Given String

  1. Hint 1

    A word longer than s can never be a prefix of it.

  2. Hint 2

    Otherwise compare the word against the first len(word) characters of s.

  3. Hint 3

    Duplicated words count once each — do not deduplicate.

How to solve Count Prefixes of a Given String

For each word, check whether s starts with it. Most languages have a built-in startsWith; otherwise compare the leading slice.

Approach

  1. For each word, reject it immediately if it is longer than s.
  2. Compare it against s's first word.length characters.
  3. Count the matches.

Why it works

The length check comes first because slicing past the end of s silently returns a shorter string in some languages and throws in others — guarding on length makes the comparison correct everywhere. Building a set of s's prefixes up front would also work and is faster when words is huge.

Complexity

  • Time — O(n · m) where m is the length of s
  • Space — O(1)

Pitfalls

  • Equal strings count — a word may be the whole of s.
  • Duplicates in words are counted separately.
  • "Prefix" means from the start, not "contained anywhere".

Reference solution

Python

from typing import List

def countPrefixes(words: List[str], s: str) -> int:
    return sum(1 for w in words if s.startswith(w))

Java

public static int countPrefixes(String[] words, String s) {
    int count = 0;
    for (String w : words) {
        if (s.startsWith(w)) count++;
    }
    return count;
}

C++

int countPrefixes(vector<string>& words, string s) {
    int count = 0;
    for (auto& w : words) {
        if (w.size() <= s.size() && s.compare(0, w.size(), w) == 0) count++;
    }
    return count;
}

JavaScript

var countPrefixes = function(words, s) {
    var count = 0;
    for (var i = 0; i < words.length; i++) {
        var w = words[i];
        if (w.length <= s.length && s.slice(0, w.length) === w) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings