iOS Interview - Leetcode 3. Longest Substring Without Repeating Characters

July 17, 2024 • 2 min read • #swift, #interview, #leetcode

Leetcode: 3. Longest Substring Without Repeating Characters

Solution

Primary idea: Dynamic sliding window tracking the last occurences of the characters in the string
Time Complexity: O(N), where N is the length of input string.
Space Complexity: O(K), where K represents the number of unique characters stored in charCount dictionary.

func lengthOfLongestSubstring(_ s: String) -> Int {
    var left = 0, right = 0, longest = 0
    var charToLatestIndex = [Character: Int]()
    var characters = Array(s)
    
    // The while loop iterates through the string and stores the character in the current index inside char.
    while right < characters.count {
        let char = characters[right]
        
        // It checks if char has been seen before by looking it up in charCount.
        // If char is found in charCount, it means it's a repeating character, and i needs to be adjusted to point to the current index of this character.
        // This adjustment is done using max(i, lastIndex + 1).
        if let lastIndex = charToLatestIndex[char] {
            left = max(left, lastIndex + 1)
        }
        
        // The current index for the char is updated in the dictionary charCount.
        // And the width of the window is calculated j - i + 1.
        // longest is updated to store the max width. Finally, j pointer moves to the right, expanding the window.
        charToLatestIndex[char] = right
        longest = max (longest, right - left + 1)
        
        right += 1
    }
    
    return longest
}

print(lengthOfLongestSubstring("abcabcbb")) // 3 (abc)
print(lengthOfLongestSubstring("bbbbb")) // 1 (b)
print(lengthOfLongestSubstring("pwwkew")) // 3 (wke)
print(lengthOfLongestSubstring("GEEKSFORGEEKS")) // 7 (EKSFORG” and “KSFORGE”)

Solution

Further reading