3.longest-substring-without-repeating-characters.md

3. Longest Substring Without Repeating Characters

Test Cases

Normal Cases

Input: s = "abcadefga"
Output: 7
Explanation: The longest substring without repeating characters is "bcadefg".

Input: s = "ababca"
Output: 3

Edge / Corner Cases

• Every character is the same.

Input: s = "aaaaa"
Output: 1

Sliding Window

• Window: the longest substring without repeating characters.
• We extend our window one by one to see (moving right pointer) if character repeats, if it has repeating character then we shrink the window by moving left pointer.

private val offset = ' '

fun lengthOfLongestSubstring(s: String): Int {
    var left = 0
    var right = 0
    val sCounts = IntArray(128)
    var result = 0
    while (right < s.length) {
        sCounts[s[right] - offset]++
        while (sCounts[s[right] - offset] > 1) {
            sCounts[s[left] - offset]--
            left++
        }
        result = maxOf(result, right - left + 1)
        right++
    }
    return result
}

// Or equivalently using set
fun lengthOfLongestSubstring(s: String): Int {
    val set = HashSet<Char>()
    var left = 0
    var maxLen = 0
    for (right in 0 until s.length) {
        // We have to check before adding the right element to the set
        while (set.contains(s[right])) {
            set.remove(s[left])
            left++
        }
        // We add after checking
        set.add(s[right])
        maxLen = maxOf(maxLen, right - left + 1)
    }
    return maxLen
}

• Time Complexity: O(n), Sliding Window iterates every character exactly once.
• Space Complexity: O(k), k represents the number of different characters.