arcbjorn

thoughtbook

Sunday, December 25, 2022

Find the difference

Leetcode 389 problem.

String t is generated by random shuffling string s and then add one more letter at a random position. A function to return the letter that was added to t.

Go

  • Time complexity: O(n2)O(n^{2}) - n is a length of a second string (t)
  • Auxiliary space: O(1)O(1) - constant amount of space
import "strings"

func findTheDifference(s string, t string) byte {
    for idx, rune := range t {
        letter := string(rune)
        frequencyInT := strings.Count(t, letter)
        frequencyInS := strings.Count(s, letter)

        if (frequencyInT > frequencyInS) {
            return t[idx]
        }
    }

    return 0
}
Creative Commons Licence