Start learning free

LESSON 218 OF 438 · BRUTE FORCE

Find the Difference in Java: O(n²) 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.

Java's String class doesn't have a single-character count method, so we'll write a small static helper countChar(String s, char c) that loops through s.toCharArray() and tallies matches. Then: 
for (char i : t.toCharArray()) {
    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

    JAVA · BRUTE FORCE

    Find The Difference in Java, explained

    Problem overview

    The method findTheDifference(String s, String t) receives two strings of lowercase letters. The string t is s shuffled, with exactly one extra letter inserted somewhere. The method returns that extra letter as a char. The length of s is between 0 and 1000, and t is always one character longer.

    For s = "abcd" and t = "abcde" the answer is 'e'. For s = "" and t = "y" the answer is 'y', since the only letter of t is the added one.

    Approach: a letter is extra if t has more copies of it

    Shuffling does not change how many times each letter occurs. So t has the same letter counts as s, except that one letter has one more copy. That letter is the answer, and it is the only letter whose count differs between the two strings.

    The brute-force way to use this: for every character of t, count how often it occurs in s, count how often it occurs in t, and compare. The first character with different counts is the extra one. The letters do not need to be found in any order, because only one letter can differ.

    The price is repeated work. If t has n characters, each count walks a whole string, and it happens twice for each character, so the total is about 2 * n * n steps, which is O(n²). With strings of up to 1001 characters that is around two million steps, which is fine here, but the same letter is counted again every time it appears. Later lessons on this problem remove that repetition with a hash map and with XOR.

    Here is s = "abcd", t = "abcde". For 'a', 'b', 'c' and 'd' the counts are 1 in both strings, so the loop moves on. For 'e' the count in s is 0 and in t is 1, so 'e' is returned.

    Step by step

    1. Write a helper, static int countChar(String s, char c), above the main method. It will answer "how many times does c occur in s?". It is static because it doesn't need any object state, and the main method will call it twice per letter.
    2. Start a counter, count, at 0.
    3. Loop over the characters of s using s.toCharArray() and a char variable named ch. A String can't be used directly in a for-each loop, so the array form is the simplest way.
    4. Compare each character to c with ch == c. For char values, == compares the letters themselves, which is what you want.
    5. Add one to count on each match.
    6. Return count after the loop.
    7. In findTheDifference, loop over the characters of t. The extra letter is in t, so every candidate is there.
    8. Compare the two counts with countChar(s, i) != countChar(t, i). A difference means i is the added letter.
    9. Return that letter, and add a final return ' '. Java requires a return on every path through the method, so the compiler needs one after the loop. By the problem's guarantees the loop always returns before reaching it.

    The solution in Java

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

    The Java details worth a look:

    • No built-in count. String has no method that counts a single character, so the helper does it with a loop.
    • toCharArray() copies the string's letters into a new char[]. The string itself is immutable and stays unchanged.
    • Returning a char from a loop variable. The loop variable i has type char, so return i; matches the method's return type without any cast. The name i is a character here, not an index.
    • The final return ' ' is only there for the compiler. It is never reached for valid input.

    Complexity

    Time: O(n²), where n is the length of t. The outer loop runs at most n times, and each pass calls countChar twice, each call walking a string of about n characters.

    Space: O(n) in this form. Each toCharArray() call allocates a copy of the string, though only one copy is alive at a time and the garbage collector reclaims it. Apart from those short-lived copies, the method keeps a few variables.

    Edge cases and common mistakes

    • An empty s. With s = "" and t = "y", countChar("", 'y') is 0 and countChar("y", 'y') is 1, so 'y' is returned.
    • The extra letter is a repeat. With s = "aa" and t = "aaa" the answer is 'a'. A check like "is this letter missing from s?" fails here, since 'a' is in s. Comparing counts handles it: 2 against 3.
    • Looping over s instead of t. The extra letter is not in s unless it is a repeat, so looping over s can miss it.
    • Counting only in one string. The comparison needs both counts, because a letter that occurs many times in both strings is not the answer.
    • Using String instead of char in the helper. Comparing a char with == works. If you moved to String values, you would have to switch to equals.

    Testing

    • "abcd", "abcde" gives 'e'.
    • "", "y" gives 'y'.
    • "aa", "aaa" gives 'a'.
    • "abcd", "dbeca" gives 'e'.
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free