Start learning free

LESSON 222 OF 442 · BRUTE FORCE

Find the Difference in Go: Brute Force Letter 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 countChar(s string, c rune) int that loops through s with a for...range loop and tallies matches. Then: 
for _, i := range 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

    GO · BRUTE FORCE

    Find The Difference in Go, explained

    Problem overview

    The function findTheDifference receives two strings. The string t is the string s with its letters shuffled and one extra letter inserted somewhere. The function returns that extra letter as a rune. Both strings hold only lowercase English letters, and s can be empty.

    With s = "abcd" and t = "abcde", the letters a to d each appear once in both strings, and e appears only in t, so the answer is 'e'. With s = "" and t = "y", the answer is 'y'.

    Approach: compare letter counts

    The extra letter can't be found by asking whether it appears in s. It may well appear there already: with s = "aab" and t = "abaa" the extra letter is another a. What gives it away is the count. For every letter except the extra one, t holds exactly as many copies as s. For the extra letter, t holds one more.

    That suggests the most direct plan. Take each letter of t, count how often it occurs in s and in t, and return the first letter whose two counts differ. The extra letter always passes through that test, and no other letter does, so the first mismatch is the answer.

    This is a brute-force solution. Counting walks a whole string, and it happens for every letter of t, so the work grows with the square of the length. The lessons that follow on this problem count each string only once.

    Step by step

    1. Write a counting helper named countChar. It takes a string and a rune and returns an int. The main function uses it twice per letter, once on s and once on t, so it is worth having as its own function.
    2. Start a counter at 0 with count := 0.
    3. Loop over the string with for _, ch := range s. The _ discards the index, because only the letters matter.
    4. Compare each letter to the one being counted with ch == c.
    5. Add one to count on a match.
    6. Return the total after the loop.
    7. In findTheDifference, loop over t. The extra letter is in t by definition, so t is the string to scan.
    8. Compare the two counts for the current letter: countChar(s, i) != countChar(t, i). A difference means this letter has more copies in t.
    9. Return the letter on a mismatch, and add a fallback return after the loop. Go insists that every path through a function with a result ends in a return, even though the constraints guarantee that the loop always returns.

    The solution in Go

    func countChar(s string, c rune) int {
    count := 0
    for _, ch := range s {
        if ch == c {
            count++
        }
    }
    return count
}

func findTheDifference(s string, t string) rune {
    for _, i := range t {
        if countChar(s, i) != countChar(t, i) {
            return i
        }
    }
    return ' '
}

    The Go details worth a closer look:

    • range over a string yields runes. Each step of for _, ch := range s gives the next character as a rune, which is an alias for int32. That is why the helper's second parameter is a rune: it has the same type as ch.
    • Indexing yields bytes. Writing the helper with for i := 0; i < len(s); i++ and comparing s[i] == c does not compile: the compiler reports invalid operation: s[i] == c (mismatched types byte and rune). Go never converts between integer types implicitly. For lowercase English letters, bytes and runes hold the same numbers, but the types must still agree.
    • The result is a number. The function returns a rune, so fmt.Println(findTheDifference("abcd", "abcde")) prints 101, the code of e. To print the letter, use fmt.Printf("%c", r) or string(r).
    • The fallback value. Without the final return ' ', the code fails with missing return. The space character is arbitrary. It is never returned for valid input.
    • Unused names are errors. A declared variable that is never used, or an import that is never used, stops the build in Go. Here every name is used.

    Complexity

    Time: O(n²), where n is the length of s. The loop in findTheDifference runs at most n + 1 times, and each pass calls countChar twice. Each call walks a whole string of about n letters. In the worst case, when the extra letter comes last in t, every letter is checked. With the constraint of 1,000 letters, that is a few million steps, which is fast, but the growth is quadratic.

    Space: O(1). The function keeps a few integers and allocates nothing.

    Edge cases and common mistakes

    • Empty s. The loop runs once over a single letter, the count in s is 0 and the count in t is 1, so that letter is returned.
    • The extra letter repeats an existing one. s = "aab" and t = "abaa" return a. Counts catch this, while a membership test would not.
    • Scanning s instead of t. The extra letter might not appear in s at all, so the loop would never meet it.
    • Mixing bytes and runes. Keep the helper's parameter and the loop variable both as runes, as in the solution.
    • Recounting is the cost. A repeated letter in t triggers the same two counts again. That repeated work is what the hash-table lesson removes.

    Testing

    • s = "abcd", t = "abcde" gives e.
    • s = "", t = "y" gives y.
    • s = "aab", t = "abaa" gives a.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free