Count a Character

+10

You get a string s and a single letter c. Return how many times c appears in s. The match is case-sensitive: B and b are different characters.

Function

countChar(s: string, c: string) → integer

sstring: the string of English letters to search
cstring: the one letter to count
Returnsinteger: how many characters of s are equal to c

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s contains only English letters (a to z, A to Z).
c is exactly one English letter.

Examples

Input: s = "Mississippi"c = "s"
Output: 4
Explanation: Mississippi has an s at indices 2, 3, 5 and 6, so the answer is 4.

Input: s = "Banana"c = "b"
Output: 0
Explanation: Banana starts with a capital B, and you are looking for a small b. Nothing matches, so the answer is 0.

Follow-up

What if c could be a word of several letters, such as ss? Do overlapping matches count, and how does your loop change?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Any character of s could be a c, so you look at each one once and count the matches. Watch the case: a capital letter is a different character.

Delete every c and compare lengths

Intuition

Build a copy of s with every c removed. Each removal makes the copy one character shorter, so the difference in length is the count. For Mississippi the copy is Miiippi: 11 minus 7 is 4.

The time is O(n), but the copy takes O(n) extra memory that a counter does not need.

Algorithm

Make a copy of s that leaves out every character equal to c.
Measure the length of s and the length of the copy.
Return the length of s minus the length of the copy.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

One pass with a counter

Intuition

Count as you read instead of building a copy. A counter starts at 0 and goes up by 1 for each character equal to c. Plain equality keeps a capital letter from matching a small one.

Each character is compared once and only the counter is stored: O(n) time, O(1) space. No solution beats O(n) time, because a character you skip could be one more c.

Algorithm

Read the target letter from c and set count = 0.
Walk s one character at a time.
If the character equals the target, add 1 to count.
Return count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Pitfalls and edge cases

Ignoring case. Lower-casing both sides makes Banana with b return 1; the answer is 0.
Comparing a character with a string. In Java, C, C++, C# and Go, c arrives as a string while s[i] or s.charAt(i) is one character. Take c[0] (or c.charAt(0)) once before the loop.
Comparing strings with == in Java. String.valueOf(s.charAt(i)) == c compares object identity and is almost always false. Compare char values.
Calling strlen(s) in the loop condition in C. It rescans the string on every step, so 5 × 10^4 characters cost about 2.5 × 10^9 steps.

Frequently asked questions3

How do you count the occurrences of a character in a string?

Walk the string once with a counter that starts at 0, and add 1 each time the current character equals the one you want. That takes O(n) time and O(1) extra memory. For a case-insensitive count, lower-case both the string and the letter first.

Can I use a built-in count function in an interview?

Usually yes, as long as you can say what it costs. Python's str.count and similar functions still read the whole string, so they are O(n). Be ready to write the loop if the interviewer asks.

How would you count every character at once?

Make one pass and keep a tally per character, in a hash map or in an array of 52 counters for the English letters. After that pass, the count of any letter is a single lookup. Use this when you are asked about many letters in the same string.

def countChar(s, c):
    # Write code here

Test #1

Test #2

Arguments

s = "Mississippi"
c = "s"

Expected Output