Problem overview
The method findTheDifference receives two strings, s and t. The string t is s with its letters shuffled and one extra letter added somewhere. The method returns that extra letter as a Character.
For s = "abcd" and t = "abcde", the letters a, b, c and d appear once in each string, and e appears only in t, so the answer is "e". For s = "" and t = "y", the answer is "y". Note that the extra letter can also be a copy of a letter that s already has: with s = "ae" and t = "aea", the answer is "a".
Approach: compare letter counts
Every letter of s appears in t the same number of times, because t is a shuffle of s plus one letter. The extra letter is the only one that appears more often in t than in s. That gives a direct test for any letter: count it in s, count it in t, and see whether the two numbers differ.
The extra letter has to be in t, so the candidates are the letters of t. The brute-force plan is to walk through t and, for each letter, run the test. The first letter whose counts differ is the answer.
This is the simplest correct solution, and the first of three on this problem. Each count walks a whole string, and the test runs once per letter of t, so the cost grows with the square of the length. Counting every letter once and storing the counts, or cancelling letters with XOR, are faster ways to get the same answer.
Step by step
- Write a counting helper.
countChar(_:_:)takes a string and a character and returns anInt. Making it its own method means the main loop can ask the question in one short expression. - Start a counter at 0 with
var count = 0. It must be avarbecause it changes. - Loop over the string. A
for-inloop over aStringgives its characters one at a time, here namedch. - Compare each character with the one you are counting.
ch == cis true when they are the sameCharacter. - Add one on a match with
count += 1. - Return
countafter the loop. - In
findTheDifference, loop overt, nots, because the extra letter is guaranteed to be int. - Compare the two counts of the current letter:
countChar(s, i) != countChar(t, i). A difference means this letter is the added one. - Return that letter, and add a fallback return after the loop. Swift requires every path of a function with a result to return a value. The constraints guarantee that the loop always returns, so the fallback
" "is never used, but the compiler can't know that.
The solution in Swift
class Solution {
func countChar(_ s: String, _ c: Character) -> Int {
var count = 0
for ch in s {
if ch == c {
count += 1
}
}
return count
}
func findTheDifference(_ s: String, _ t: String) -> Character {
for i in t {
if countChar(s, i) != countChar(t, i) {
return i
}
}
return " "
}
}
Some Swift details worth a closer look:
Characteris notString. Looping over a string producesCharactervalues, andfindTheDifferencereturns one. A literal such as" "becomes aCharacterbecause the return type asks for it.- Underscores in the signature.
_ s: Stringmeans the caller writes no argument label:countChar(s, i)and notcountChar(s: s, c: i). - Parameters are constants.
sandccan't be reassigned inside the helper, which is why the running total lives in a separatevar. - Calling a method from another method. Inside a class,
findTheDifferencecallscountChardirectly; noself.is needed. - Character comparison uses
==and compares the characters themselves, not references. With lowercase letters that is all there is to it.
Complexity
Time: O(n²). Let n be the length of t. One call to countChar walks a whole string, which is about n steps. The loop makes two calls for each letter it examines, and in the worst case it examines every letter of t before it finds the difference. That is about 2n calls of about n steps each.
Space: O(1). The solution keeps one counter and a loop variable. It builds nothing that grows with the input.
With the lesson's limit of 1000 characters, the work is at most a couple of million comparisons, which is fine. The point of the later lessons is the better growth rate.
Edge cases and common mistakes
- Empty
s. Withs = "", every count insis 0 andthas one letter, so the first and only letter oftis returned. - A repeated letter. For
s = "aab"andt = "abaa"the answer is"a": it appears 2 times insand 3 times int. A solution that only checks whether a letter appears inswould find nothing here. The test must compare counts, not presence. - Looping over
s. If the extra letter isn't ins, a loop oversnever sees it. - Several letters with differing counts. This can't happen with valid input. Exactly one letter has a higher count in
t, which is why returning the first mismatch is correct. - Forgetting the final return. Without the line after the loop, the code doesn't compile, because the function has a path that returns nothing.
Testing
s = "abcd",t = "abcde"returns"e".s = "",t = "y"returns"y".s = "aab",t = "abaa"returns"a".s = "ae",t = "aea"returns"a".countChar("banana", "a")returns3, andcountChar("banana", "z")returns0.
