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 <= 10001 <= words[i].length, s.length <= 10words[i] and s consist of lowercase English letters.
Hints for Count Prefixes of a Given String
Hint 1
A word longer than
scan never be a prefix of it.Hint 2
Otherwise compare the word against the first
len(word)characters ofs.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
- For each word, reject it immediately if it is longer than
s. - Compare it against
s's firstword.lengthcharacters. - 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
wordsare 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.