Count Prefixes of a Given String

Count Prefixes of a Given String

What is this problem about?

The "Count Prefixes of a Given String interview question" is a straightforward string verification task. You are given an array of strings called words and a target string s. Your goal is to determine how many strings in the words array are prefixes of s. A string $P$ is a prefix of $s$ if $s$ starts with $P$.

Why is this asked in interviews?

Companies like Google use the "Count Prefixes of a Given String coding problem" as an introductory warm-up to test basic string manipulation and loop control. It evaluates a candidate's familiarity with string matching functions and their ability to handle basic linear scans over an array. It’s a test of clean coding and efficiency in "String interview pattern" basics.

Algorithmic pattern used

This problem follows the Linear Scan and String Matching pattern.

1. Iterate: Use a loop to go through each word in the words array.
2. Prefix Check: For each word, use a built-in function (like startsWith() in Java/JavaScript or s.startswith() in Python) to check if the target string s begins with that word.
3. Count: Increment a counter for every successful match.
4. Optimization: Since we are only checking prefixes, if a word's length is greater than the length of $s$, it can be skipped immediately.

Example explanation

Words: ["a", "b", "c", "ab", "bc", "abc"], $s = "abc"$

• "a" is a prefix of "abc". (Count = 1)
• "b" is not a prefix.
• "c" is not a prefix.
• "ab" is a prefix of "abc". (Count = 2)
• "bc" is not a prefix.
• "abc" is a prefix of "abc". (Count = 3) Result: 3.

Common mistakes candidates make

• Subsegment Confusion: Checking if the word is anywhere in the string (substring) instead of specifically at the beginning (prefix).
• Case Sensitivity: Not clarifying if the comparison should be case-sensitive.
• Empty String: Forgetting how the logic handles an empty string in the words array (an empty string is usually considered a prefix of any string).

Interview preparation tip

Get comfortable with your programming language's string manipulation library. Knowing the difference between "contains," "prefix," and "suffix" methods is a foundational skill for any "String interview pattern" problem.