Start learning free

LESSON 218 OF 438 · BRUTE FORCE

Find the Difference in Python: Brute Force with count()

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.

Python strings have a built-in count() method. s.count(i) returns how many times i appears in s. So we can write: 
for i in t:
    if s.count(i) != t.count(i):
        return i


This brute-force approach is O(n2) because each count() 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 3
    Ctrl + Enter to check

    PYTHON · BRUTE FORCE

    Find The Difference in Python, explained

    Problem overview

    The method findTheDifference receives two strings, s and t. The string t was built by shuffling the letters of s and inserting one extra letter at a random position. The method returns that extra letter. Both strings use lowercase English letters, s may be empty, and t is always exactly one character longer than s.

    For s = "abcd" and t = "abcde", the letters a, b, c and d appear once in each string, while e appears only in t, so the answer is "e". For s = "" and t = "y" the answer is "y".

    Approach: compare how often each letter occurs

    Shuffling does not change how many times each letter occurs. So every letter of s occurs exactly as often in t as in s, except for one letter: the added one occurs once more in t. That gives a direct test for any letter: count it in both strings, and if the two counts differ, that letter is the answer.

    The added letter can be a letter that is already in s. With s = "ab" and t = "aba", the extra letter is a: it occurs once in s and twice in t. Checking only whether a letter is missing from s would fail here, which is why the test compares counts instead.

    The extra letter is always in t, so the loop walks through t and tests each of its letters. Python strings have a count() method that returns how many times a substring occurs, which makes the test a single comparison.

    This is the brute-force approach. Every count() call reads a whole string, and it is called for each of the n letters of t, so the total work grows like n². With strings up to 1000 characters that is fast enough, and it is the simplest correct solution. Later lessons on this problem keep the counts instead of recomputing them, and then reduce the idea to a single number.

    Step by step

    1. Loop over t. The loop variable i takes each letter of t in turn. Looping over t rather than s matters because the answer exists only in t.
    2. Compare the two counts. Inside the loop, an if checks whether s.count(i) differs from t.count(i). For every ordinary letter the counts are equal. For the added letter, the count in t is one higher.
    3. Return the letter. Exactly one letter has mismatched counts, so the method can return it as soon as the check succeeds. There is no need to look at the rest of t.

    The solution in Python

    class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        for i in t:
            if s.count(i) != t.count(i):
                return i

    Python details worth knowing:

    • Iterating a string. for i in t gives one-character strings, so i is a string such as "e", and returning it matches the declared -> str.
    • count() counts non-overlapping occurrences. "banana".count("a") is 3. Here the argument is always a single character, so overlap never comes up.
    • No return at the end. If the loop finished without returning, the method would give back None. That cannot happen when the input follows the statement, because the added letter always has a higher count in t.

    Complexity

    Time: O(n²), where n is the length of t. The loop runs up to n times, and each iteration makes two count() calls, each reading a string of length n - 1 or n. Repeated letters are counted again every time they appear.

    Space: O(1). The method keeps only the loop variable.

    Edge cases and common mistakes

    • Empty s. For s = "" and t = "y", "".count("y") is 0 and "y".count("y") is 1, so the method returns "y".
    • The extra letter repeats an existing one. s = "ab", t = "aba" returns "a", because the counts of a are 1 and 2.
    • Looping over s by mistake. If the extra letter is not in s, the loop never visits it. Loop over t.
    • Checking only membership. if i not in s finds a brand-new letter but misses a repeated one such as the second a above.
    • Shuffled order. The position of the extra letter and the order of the other letters do not matter, since counts ignore order. s = "abcd" with t = "dcbae" still returns "e".

    Testing

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