RSSAmplifier

Swift by An Tran · Jul 17, 2024

iOS Interview - Leetcode 3. Longest Substring Without Repeating Characters

0
Sign in to vote or save

This page did not load. You can still read it on the original site — the toolbar below keeps your place in the directory.

Leetcode: 3. Longest Substring Without Repeating Characters Solution Primary idea: Dynamic sliding window tracking the last occurences of…

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”)

Further reading

Read on antran.app

Comments

Nothing yet. Say the first thing.

    Sign in to join the conversation.