Solution.kt

package problems.lengthOfLongestSubstring

import readmeGeneration.ProblemDifficulty
import readmeGeneration.ProblemSolution

/*
Given a string s, find the length of the longest substring without repeating characters.

Example 1:
    Input: s = "abcabcbb"
    Output: 3
    Explanation: The answer is "abc", with the length of 3.

Example 2:
    Input: s = "bbbbb"
    Output: 1
    Explanation: The answer is "b", with the length of 1.

Example 3:
    Input: s = "pwwkew"
    Output: 3
    Explanation: The answer is "wke", with the length of 3.
    Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:
    Input: s = ""
    Output: 0
 */

@ProblemSolution(3, "Longest Substring Without Repeating Characters", ProblemDifficulty.MEDIUM,
    "https://leetcode.com/problems/longest-substring-without-repeating-characters/")
class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        var maxLength = 0
        var startIdx = 0
        val lastKnownPositions = HashMap<Char, Int>()

        for ((idx, c) in s.withIndex()) {
            val knownIdx = lastKnownPositions[c]
            if (knownIdx != null && startIdx <= knownIdx) {
                startIdx = knownIdx + 1
            }

            val curLength = idx - startIdx + 1
            if (curLength > maxLength) {
                maxLength = curLength
            }
            lastKnownPositions[c] = idx
        }

        return maxLength
    }
}