Start learning free

LESSON 221 OF 441 · BRUTE FORCE

Find the Difference in C#: Brute Force Counting

Practice O(n2) 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 foreach and tallies matches. Then: 
foreach (char i in t) {
    if (CountChar(s, i) != CountChar(t, i)) {
        return i;
    }
}


This brute-force approach is O(n2) 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
    Ctrl + Enter to check

    C# · BRUTE FORCE

    Find The Difference in C#, explained

    Problem overview

    The method FindTheDifference receives two strings. t contains every letter of s, shuffled, plus exactly one extra letter at some position. The method returns that extra letter as a char.

    With s = "abcd" and t = "abcde", the answer is 'e'. With s = "" and t = "y", nothing was shuffled and the answer is 'y'. The strings hold only lowercase letters, and s has at most 1000 of them.

    Approach: compare letter counts

    The extra letter is a letter of t, so it is enough to look at the letters of t one at a time and ask whether each one is the extra one.

    A first idea is to check whether the letter appears in s at all. That fails when the added letter is one s already contains. For s = "aab" and t = "abab", every letter of t is in s, yet the added letter is the second 'b'.

    The reliable test is a count. A letter is the extra one exactly when it appears more times in t than in s. For every other letter the counts are equal, because t is a shuffle of s plus one letter. Only one letter can have different counts, so the first mismatch found is the answer.

    Counting a letter means walking a whole string, and the method does that for every letter of t. With n letters in s, that is about n letters times two walks of length n or so: O(n²). It is the simplest correct solution and a good starting point. Storing the counts once in a dictionary, or cancelling letters with XOR, brings the time down to O(n); those are other lessons.

    Step by step

    1. Write a counting helper. CountChar(string s, char c) returns how many times c appears in s. It sits above FindTheDifference on the same Solution class, and the main method calls it twice per letter.
    2. Start a counter at 0, an int named count.
    3. Loop over the string with foreach (char ch in s). Looping over a string gives its characters one at a time.
    4. Compare each character with the one being counted: ch == c. For char values, == compares the characters themselves.
    5. Add one to count when they match.
    6. Return count after the loop.
    7. In FindTheDifference, loop over t. The extra letter is guaranteed to be there, so these are the only candidates.
    8. Compare the counts. If CountChar(s, i) != CountChar(t, i), the letter i appears more often in t, so it is the extra one.
    9. Return i from inside the if, and return a placeholder after the loop. C# requires every path through a method with a return type to return a value. The constraints guarantee that the loop always finds the letter, so the final return ' ' is never reached on valid input; it only satisfies the compiler.

    The solution in C#

    class Solution {
    public int CountChar(string s, char c) {
        int count = 0;
        foreach (char ch in s) {
            if (ch == c) {
                count++;
            }
        }
        return count;
    }
    public char FindTheDifference(string s, string t) {
        foreach (char i in t) {
            if (CountChar(s, i) != CountChar(t, i)) {
                return i;
            }
        }
        return ' ';
    }
}

    The C# details worth knowing:

    • char is a single UTF-16 code unit. It has its own literal syntax, 'e' with single quotes, while "e" with double quotes is a one-letter string. The method returns a char, so the answer is 'e'.
    • Which letter is returned. The loop walks t from the left and returns the first letter whose counts differ. When the extra letter is a repeat of one already in s, every copy of that letter has the same counts, so the result is still that letter. For s = "aab" and t = "abab" the method returns 'b'.
    • The helper is reused. CountChar(s, i) and CountChar(t, i) are called with the same letter on both strings, so the two counts are directly comparable.
    • The helper's name. It is a public method on Solution next to the one the tests call. C# method names are case-sensitive, so CountChar and countChar are different names.

    Complexity

    Time: O(n²), where n is the length of the strings. The loop runs at most n + 1 times. Each iteration calls CountChar twice, and each call walks a whole string of n or n + 1 letters. With n up to 1000, that is a couple of million steps, which is fast. The same code would be too slow for strings of millions of letters.

    Space: O(1). The method keeps only a few int and char variables.

    Edge cases and common mistakes

    • Empty s. With s = "" and t = "y", CountChar(s, 'y') is 0 and CountChar(t, 'y') is 1, so the method returns 'y'.
    • The extra letter repeats a letter of s. s = "zz" and t = "zzz" returns 'z'. Checking whether a letter is present in s gets this wrong, which is why the lesson compares counts.
    • Counting only in s or only in t. One count alone says nothing. The test is the difference between the two.
    • Forgetting the final return. Without return ' ', the compiler reports that not all code paths return a value.
    • Using double quotes for a letter. CountChar(s, "a") doesn't compile because "a" is a string, not a char.

    Testing

    • s = "abcd", t = "abcde" gives 'e'.
    • s = "", t = "y" gives 'y'.
    • s = "aab", t = "baab" gives 'b'.
    • s = "ab", t = "bca" gives 'c'.
    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