Start learning free

LESSON 222 OF 442 · BRUTE FORCE

Find the Difference in Kotlin: Brute Force with Character Counts

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 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

    KOTLIN · BRUTE FORCE

    Find The Difference in Kotlin, explained

    Problem overview

    You get two strings, s and t. The string t is s with its letters shuffled and one extra letter inserted somewhere. findTheDifference must return that extra letter as a Char.

    For s = "abcd" and t = "abcde" the answer is 'e', because t holds every letter of s plus an e. For s = "" and t = "y" the answer is 'y': with nothing to shuffle, the extra letter is the whole of t. Both strings use lowercase letters only, and t is always exactly one character longer than s.

    Approach: compare how often each letter occurs

    Shuffling doesn't change how many times each letter occurs, so the position of letters is useless here. What changes is the count: the added letter occurs one more time in t than in s, and every other letter occurs equally often in both.

    That gives a direct plan. Take each character of t in turn, count it in s, count it in t, and stop at the first character whose two counts differ. The extra letter must be among the characters of t, so scanning t is guaranteed to reach it. Scanning s instead would fail whenever the extra letter doesn't appear in s at all.

    The plan is brute force: every character of t triggers two full passes over a string. It is the simplest correct approach and a good first version. The later lessons on this problem replace the repeated counting with a stored count table and then with XOR.

    Take s = "ab" and t = "bab". The first character of t is b. It occurs once in s and twice in t, so the counts differ and the function returns 'b' right away. This shows that the extra letter can be a copy of a letter s already has, so checking whether s contains it would not be enough. You have to compare counts.

    Here is the first example in full, s = "abcd" and t = "abcde". For a the counts are 1 and 1, and the same holds for b, c and d, so the loop moves on each time. For e the count in s is 0 and in t is 1. That is the first mismatch, so the function returns 'e'. Because the loop returns on the first mismatch and exactly one letter can mismatch, the order of the characters in t doesn't matter.

    Step by step

    1. Add a helper, countChar(s: String, c: Char): Int, to the Solution class. The main method calls it twice per character, so it is worth naming.
    2. Start a counter. A var count = 0 is the running tally. It is a var because it changes.
    3. Loop over the string. for (ch in s) walks through the characters of s from left to right.
    4. Test each character. ch == c asks whether this character is the one being counted.
    5. Increment on a match. count++ adds one.
    6. Return the tally after the loop.
    7. In findTheDifference, loop over t. The extra letter is in t, so every candidate comes from there.
    8. Compare the counts. If countChar(s, i) != countChar(t, i), this letter occurs more often in t, which makes it the added one.
    9. Return it immediately, and add a fallback return after the loop so that every path returns a Char.

    The solution in Kotlin

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

    Kotlin details worth a look:

    • A String can be looped over directly. for (i in t) gives one Char per turn, so no index is needed.
    • Char against String. A single character is written with single quotes, 'e', and has type Char. Double quotes make a String, which wouldn't match the declared return type.
    • == on characters compares their values, which is what ch == c needs.
    • The last return ' ' is required. The compiler can't know that the loop always finds a mismatch. Without that line it reports missing return statement. For valid input the line never runs.
    • count++ and var. count is an Int declared with var, so it can be reassigned, and ++ adds one to it. A val would not allow that. The method's declared return type, Int, matches it.
    • Members call each other by name. countChar sits in the same class, so findTheDifference calls it without any prefix.

    Complexity

    Time: O(n²), where n is the length of t. Each countChar call walks a whole string, which costs O(n), and the loop makes two calls for each of up to n characters. With strings of at most 1000 letters that is a few million steps at worst, which is fine here but wasteful.

    Space: O(1). The function keeps one counter and the loop variable. It never builds a table.

    Edge cases and common mistakes

    • Empty s. countChar("", 'y') is 0 while countChar("y", 'y') is 1, so 'y' is returned.
    • The extra letter repeats an existing one. With s = "aab" and t = "baab", the count of a is 2 in both strings and the count of b is 1 against 2. The function returns 'b'.
    • Looping over s. A letter that never appears in s would never be examined.
    • Using a membership test. Asking whether s contains the letter fails as soon as the added letter is a duplicate.
    • Dropping the fallback return. The code doesn't compile without it.

    Testing

    • s = "abcd", t = "abcde" gives 'e'.
    • s = "", t = "y" gives 'y'.
    • s = "aab", t = "baab" gives 'b'.
    • s = "ab", t = "bab" gives 'b'.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free