Start learning free

LESSON 225 OF 445 · BRUTE FORCE

Find the Difference in Rust: Brute Force Counting

Practice O(n²) 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 count_char(s: &str, c: char) -> i32 that loops through s.chars() and tallies matches. Then:

for i in t.chars() {
    if Self::count_char(s, i) != Self::count_char(t, i) {
        return i;
    }
}

This brute-force approach is O(n²) because each count_char 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

Guided

Ctrl + Enter to check

RUST · BRUTE FORCE

Find The Difference in Rust, explained

Problem overview

The function find_the_difference receives two string slices, s and t. The string t is s shuffled, with exactly one extra lowercase letter inserted somewhere. The function returns that extra letter as a char. The string s can be empty, and t is always one character longer.

For s = "abcd" and t = "abcde" the answer is 'e': every letter of s appears once in t, and e is the only one left over. For s = "" and t = "y" the answer is 'y'.

Approach: compare letter counts

The extra letter is a letter of t that appears more often in t than in s. A letter that was already in s has the same count in both strings, and a letter that wasn't in s has count 0 there and at least 1 in t. Only the added letter breaks the equality, because exactly one letter was added.

That gives a plan with no cleverness: take each character of t, count how often it occurs in s and in t, and return the first character where the two counts differ. The tool for that is a small helper that counts occurrences of one character in a string.

This is the brute-force version. Each call of the helper walks a whole string, and it is called twice for every character of t, so the total work grows with the square of the length. Later lessons on this problem build the counts once with a hash map and then drop counting altogether with XOR. Here the goal is to get a correct, readable answer first.

Here is the idea on s = "ab" and t = "abb". The first character of t is a: one in s, one in t, equal. The second is b: one in s, two in t, different, so the function returns 'b'. The function returns that way for the strings "aa" and "aaa" as well: the count of a is 2 in s and 3 in t.

Step by step

Define the helper first. count_char(s: &str, c: char) -> i32 sits in the same impl Solution block, above find_the_difference. It borrows the string, so the caller keeps it.
Start a counter at 0. It must be let mut, because it changes.
Loop over s.chars() with the loop variable ch. A String or &str isn't indexed by character in Rust, so chars() is how you visit each one.
Compare ch == c. Both are char values, so the comparison is direct.
Add one to the counter on a match.
Return the counter after the loop.
Loop over t.chars() in the main function. The extra letter is in t, so every candidate comes from there.
Compare the two counts by calling the helper on s and on t for the current letter. The call is written Self::count_char(...), because the helper takes no self.
Return the letter when the counts differ. After the loop, return a placeholder character: Rust needs a value on every path, even one the constraints make unreachable.

The solution in Rust

impl Solution {
    fn count_char(s: &str, c: char) -> i32 {
        let mut count = 0;
        for ch in s.chars() {
            if ch == c {
                count += 1;
            }
        }
        return count;
    }
    fn find_the_difference(s: &str, t: &str) -> char {
        for i in t.chars() {
            if Self::count_char(s, i) != Self::count_char(t, i) {
                return i;
            }
        }
        return ' ';
    }
}

Running it on the examples gives 'e' for ("abcd", "abcde"), 'y' for ("", "y") and 'q' for ("xyz", "zyxq").

The Rust details worth a closer look:

Type inference. let mut count = 0; has no type written, and the compiler infers i32 from the function's return type.
chars() yields char values. Each is a Unicode scalar value, four bytes wide, not a single byte. For lowercase English letters that makes no practical difference here.
return is optional at the end. The last expression of a block, written without a semicolon, is its value. The lesson uses explicit return statements, which are valid, though idiomatic Rust would write count alone on the last line.
The same counting in one expression. s.chars().filter(|&ch| ch == c).count() gives the same number. It is a usize, so it would need a cast to match the i32 in the signature.
Borrowed strings. Both parameters are &str, so passing s to the helper twice doesn't move it. Passing a String by value would move it on the first use.
The placeholder. The final return ' '; is never reached when the input follows the rules, but removing it is a compile error, since the function must return a char on every path.

Complexity

Let n be the length of t.

Time: O(n²). The loop runs up to n times. Each iteration calls count_char twice, once over s (length n - 1) and once over t (length n), so each iteration costs O(n). With the length capped at 1000 this is fast enough, but it is the slowest of the approaches to this problem.

Space: O(1). The helper keeps one counter, and nothing grows with the input.

Edge cases and common mistakes

Empty s. The helper returns 0 for every letter on an empty string, so the first letter of t already differs. ("", "y") returns 'y'.
The extra letter is a repeat. For ("aa", "aaa"), the letter exists in both strings, so a check like "is it missing from s?" fails. Comparing counts is what handles this case.
Looping over s instead of t. The added letter might not be in s at all, so looping over s can never find it. The candidates come from t.
Forgetting Self::. Writing count_char(s, i) inside the impl block is a compile error: associated functions are reached through Self:: or Solution::.
Forgetting mut. Without let mut, count += 1 is rejected, because the variable can't be assigned twice.

Testing

s = "abcd", t = "abcde" gives 'e'.
s = "", t = "y" gives 'y'.
s = "ab", t = "abb" gives 'b'.
s = "aa", t = "aaa" gives 'a'.
s = "xyz", t = "zyxq" gives 'q'.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free