Count a Character

Q: Is counting a character case-sensitive?

In this problem, yes: B and b are different characters, so Banana contains no b . If you need a case-insensitive count instead, convert both the string and the letter to lower case before you compare.

BeginnerArrays and strings

+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, so only exact copies of c count.

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 positions 2, 3, 5 and 6, counting from 0, so the answer is 4.

Input: s = "Banana"c = "b"
Output: 0
Explanation: Banana starts with a capital B, and the search is for a small b. The two differ, so nothing matches and the answer is 0.

+18 hidden tests on Submit

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

Every character of s has to be looked at once, because any of them could be a c. The work is a single pass with a counter. The details that trip people up are case (a capital letter is a different character) and, in some languages, comparing a character with a one-letter string.

Delete every c and compare lengths

Intuition

Build a copy of s with every c removed. Each removed character makes the copy one shorter, so the difference between the two lengths is exactly the number of times c appeared. Most languages have a replace or delete function that does the removal for you.

For Mississippi and s, the copy is Miiippi. That is 7 characters against the original 11, so c appeared 4 times. With Banana and b, nothing is removed because the capital B does not match, and the difference is 0.

The work is one pass over s, so the time is O(n). The cost is memory: the copy can be as long as s, which is O(n) extra space 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

Skip the copy and count as you read. Walk s from left to right with a counter that starts at 0, and add 1 whenever the current character equals c. A match is decided by plain equality, so a capital letter never matches a small one.

For Mississippi, the counter rises at indices 2, 3, 5 and 6 and ends at 4. Every character is compared once, and nothing else is stored.

That gives O(n) time and O(1) extra space: one counter and the target letter. You cannot do better on 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

The loop is short, and the bugs hide in how the two values are compared.

Ignoring case. Lower-casing both sides makes Banana with b return 1, but the task asks for exact matches, so the answer is 0.
Comparing a character with a string. In Java, C, C++, C# and Go, c arrives as a string while s.charAt(i) or s[i] is a single 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, or use equals.
Calling strlen(s) in the loop condition in C. It walks the whole string on every step, so 5 × 10^4 characters cost about 2.5 × 10^9 steps. Stop at the '\0' terminator instead.

Frequently asked questions4

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

Start a counter at 0 and walk the string once. Each time the current character equals the one you are looking for, add 1. When the loop ends, the counter is the answer, and the run takes O(n) time with O(1) extra memory.

Is counting a character case-sensitive?

In this problem, yes: B and b are different characters, so Banana contains no b. If you need a case-insensitive count instead, convert both the string and the letter to lower case before you compare.

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). Many interviewers then ask you to write the loop yourself, so be ready to show it.

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. This is the better plan when you are asked about many letters for the same string.

Python

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

Test cases

Case 1

Case 2

Input

s = "Mississippi"
c = "s"

Expected