Start learning free

LESSON 222 OF 442 · BRUTE FORCE

Find the Difference in Scala: Brute Force with 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: Char): Int that loops through s and tallies matches. Then: 
for (i <- 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

    SCALA · BRUTE FORCE

    Find The Difference in Scala, explained

    Problem overview

    You get two strings, s and t. The string t was made by shuffling the letters of s and inserting one extra letter somewhere. The method findTheDifference must return that extra letter as a Char.

    For s = "abcd" and t = "abcde", the letters a, b, c and d each appear once in both strings, while e appears once in t and never in s. The answer is 'e'. For s = "" and t = "y", the answer is 'y', because t is nothing but the added letter.

    Both strings contain only lowercase letters, and s can be empty, with at most 1000 characters. The shuffling means the extra letter can be anywhere in t, so looking at the last character is not enough.

    Approach: compare letter counts

    The extra letter is the one that occurs more often in t than in s. If the added letter is a brand-new one, it occurs once in t and zero times in s. If it duplicates a letter already in s, say s = "aab" and t = "abaa", the count of a rises from two to three. In both cases exactly one letter has different counts in the two strings, and every other letter has equal counts.

    That gives a direct plan. Take each character of t, count how often it occurs in s and in t, and return the first one where the two counts differ. Counting is a small loop, so it goes into a helper method, countChar.

    This is the brute-force version. Every call to countChar walks a whole string, and the main loop makes two calls per character of t. With n the length of t, that is about 2n walks of up to n characters each, so the time is O(n²). For strings of at most 1001 characters that is fast enough, and the idea is easy to get right. Later lessons on this problem keep the counts in a hash map, and then in a single number, to reach O(n).

    Step by step

    1. Define the helper. countChar(s: String, c: Char): Int belongs to the Solution class, above findTheDifference. It answers one question: how many times does c occur in s?
    2. Start a counter. A var count = 0 holds the running total. It must be a var because it changes.
    3. Loop over the string. for (ch <- s) gives each character in turn, as a Char.
    4. Compare and increment. When ch == c, add one to count. Then the loop ends and the method returns count.
    5. Loop over t in the main method. The extra letter is certainly a character of t, so these are the only candidates worth testing.
    6. Test each candidate. If countChar(s, i) != countChar(t, i), the letter occurs a different number of times in the two strings. It can only be the added one, so return it.
    7. Add a fallback. After the loop the method returns a space. Scala needs a Char on every path, and the compiler can't know the loop always returns. With valid input the fallback is never reached.

    The solution in Scala

    class Solution {
    def countChar(s: String, c: Char): Int = {
        var count = 0
        for (ch <- s) {
            if (ch == c) {
                count += 1
            }
        }
        return count
    }
    def findTheDifference(s: String, t: String): Char = {
        for (i <- t) {
            if (countChar(s, i) != countChar(t, i)) {
                return i
            }
        }
        return ' '
    }
}

    The Scala details worth a closer look:

    • for (ch <- s) on a String. A string behaves like a sequence of characters, so a for loop can walk it directly. The loop variable has type Char, which is why ch == c compares two characters.
    • == compares values. For Char and for strings, == checks equality of contents, so there is nothing like Java's reference comparison to worry about.
    • return inside the loop. The body of a for loop is a function that Scala passes to foreach, and return inside it still leaves the whole method. Scala 3.5 accepts this but reports a warning that non-local returns are no longer supported. The idiomatic alternatives avoid the loop, for example t.find(c => countChar(s, c) != countChar(t, c)), which returns an Option[Char].
    • The return type. The method is declared to return Char, so every path ends in a Char. A bare return i with i a Char fits, and so does the fallback ' ', a character literal in single quotes. A string literal in double quotes would not compile there.
    • Counting without a helper. A shorter way to write countChar is s.count(_ == c). The lesson writes the loop out so you can see what the counting does.

    Complexity

    Time: O(n²). countChar costs time proportional to the length of its string. The main loop runs at most n times with two calls each, and every call walks up to n characters. The loop can end early, but in the worst case the extra letter sits at the end of t.

    Space: O(1). Only a few integers and a character exist at any time. No copy of either string is made.

    Edge cases and common mistakes

    • Empty s. With s = "", countChar(s, i) is 0 for every character, and t has one character with a count of 1. The first iteration returns it.
    • The extra letter duplicates an existing one. For s = "aab" and t = "abaa", the count of a is 2 in s and 3 in t, so 'a' is returned. Checking only whether the letter appears in s would fail here.
    • Looking at s instead of t. Looping over s can miss a brand-new letter, because that letter is not in s at all. Loop over t.
    • Returning a String. The result is a Char, written 'e', not "e".
    • A val counter. count += 1 on a val is a compile error, so the counter has to be a var.

    Testing

    • s = "abcd", t = "abcde" returns 'e'.
    • s = "", t = "y" returns 'y'.
    • s = "abcd", t = "dbeca" returns 'e'.
    • countChar("banana", 'a') returns 3.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free