Start learning free

LESSON 217 OF 437 · BRUTE FORCE

Find the Difference in C++: Brute Force with Counting

Practice O(n²) Read the full explanation

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: e
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: y

Constraints:

0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lowercase English letters.

The extra letter has to be a letter that appears in t. So we can iterate through every character of t and ask: "is this the extra one?"

A character i is the extra one if and only if it appears more times in t than in s. We can compare the count of i in both strings.

We'll write a small helper int countChar(string s, char c) that loops through s with a range-based for and tallies matches. Then:

for (char i : t) {
    if (countChar(s, i) != countChar(t, i)) {
        return i;
    }
}

This brute-force approach is O(n²) because each countChar call walks the whole string, and we do it for every character. It's the simplest place to start; later solutions improve to O(n).

STEP 1 OF 9

Guided

Ctrl + Enter to check

C++ · BRUTE FORCE

Find The Difference in C++, explained

Problem overview

The method findTheDifference receives two strings. The string t was built from s by shuffling its letters and inserting one extra letter at a random position. The method must return that extra letter as a char. Both strings hold lowercase English letters only, s can be empty, and t is always exactly one character longer.

With s = "abcd" and t = "abcde", every letter of s appears once in t, and e appears once more with nothing to pair it with, so the answer is 'e'. With s = "" and t = "y" there is nothing to pair at all, and the answer is 'y'.

Approach: ask each letter of t whether it is the extra one

The extra letter is a letter of t, so the search can walk through t and test each character. The test comes from the way t is built: a letter is the extra one exactly when it occurs more times in t than in s. For every other letter the two counts are equal, because shuffling doesn't change how many copies a letter has.

That gives a plan with two parts. A small helper counts how often a character occurs in a string. The main loop then compares countChar(s, i) with countChar(t, i) for each character i of t and returns the first character where they differ.

Try s = "aab" and t = "abaa". The first character of t is a. It occurs 2 times in s and 3 times in t, so the counts differ and 'a' is returned. Had the loop started on a different letter, such as b (1 and 1), it would have moved on.

This is the simplest correct idea, which makes it a good starting point. It is slow, though: each call to countChar walks a whole string, and the loop makes two calls per character of t. That is O(n²) overall. Later lessons on this problem count with a hash table in O(n) time and then use XOR to need no extra memory.

Step by step

Define the helper first. countChar(string s, char c) lives on the Solution class above findTheDifference. Counting is a job you repeat twice per character, so it deserves its own name.
Start a counter at zero. The variable count collects the number of matches.
Loop over the string with a range-based for that gives each character as ch.
Compare each character with c. Only equal characters should be counted.
Increment count inside the if.
Return count after the loop. It is the number of times c occurred.
Loop over t in the main method. The extra letter is in t, so there is no point looping over s.
Compare the two counts. A mismatch means i occurs more often in t than in s.
Return i on a mismatch. Add a fallback return after the loop as well: C++ expects a return on every path. Given the constraints the loop always returns first.

The solution in C++

class Solution {
public:
    int countChar(string s, char c) {
        int count = 0;
        for (char ch : s) {
            if (ch == c) {
                count++;
            }
        }
        return count;
    }
    char findTheDifference(string s, string t) {
        for (char i : t) {
            if (countChar(s, i) != countChar(t, i)) {
                return i;
            }
        }
        return ' ';
    }
};

C++ details worth a closer look:

A char is a small integer. ch == c compares character codes, so it is a plain, cheap comparison. A std::string is a sequence of these, and the range-based for (char ch : s) visits them in order.
Parameters are copies. countChar(string s, char c) takes the string by value, so each call copies the whole string before counting. That is harmless for strings of up to 1000 characters but wasteful. Declaring the parameter as const string& s would avoid the copy without changing the logic. The lesson keeps the by-value version for simplicity.
The fallback return. The compiler can't know that the constraints guarantee an answer, and flowing off the end of a function that returns a value is undefined behaviour. The trailing return ' '; never runs for valid input and only closes the path.
A helper inside the class. countChar is a member function, so findTheDifference calls it by name. Member functions of a class can be used in any order, so it doesn't matter that the helper is written first.

Complexity

Time: O(n²), where n is the length of t. The loop runs at most n times, and each iteration makes two calls that walk strings of length n - 1 and n. The loop can stop early, but in the worst case the extra letter is the last one examined.

Space: O(n) as written, because each by-value call copies a string. With const string& parameters the extra space would be O(1).

Edge cases and common mistakes

Empty s. t then has one character, which has count 0 in s and 1 in t, so it is returned immediately.
The extra letter duplicates an existing one. With s = "a" and t = "aa" the answer is 'a'. Checking whether the letter merely exists in s would fail here, which is why the test compares counts instead.
Looping over s instead of t. The extra letter is not in s unless it is a duplicate, so the loop would miss it.
Returning a count. The method returns the letter itself, a char, not how many times it occurs.
Counting with = instead of ==. if (ch = c) compiles and assigns, which gives wrong counts. Use the double equals sign.

Testing

s = "abcd", t = "abcde" gives 'e'.
s = "", t = "y" gives 'y'.
s = "aab", t = "abaa" gives 'a'.
s = "a", t = "ab" gives 'b'.

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free