Get started

Count Prefixes of a Given String — Easy Problem & Solution

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.

  • 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.

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))

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue