leetcode: 3. Longest Substring Without Repeating Characters

problem

• https://leetcode.com/problems/longest-substring-without-repeating-characters/

Brute Force

• O(N^2) time

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {        
        val size = s.length
        var answer = 0
        
        for (i in 0 until size) {
            val table = mutableMapOf<Char, Int>()
            table[s[i]] = 1
            var temp = 1
            for (j in i + 1 until size) {
                if (table[s[j]] != null) break
                else {
                    table[s[j]] = 1
                    temp++
                }
            }
            answer = maxOf(answer, temp)
        }
        return answer
    }
}

Hash Table

• O(N) time

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {   
        if (s == "") return 0
        
        val size = s.length
        var answer = 1
        val table = mutableMapOf<Char, Int>()
        var start = 0
        for (i in 0 until size) {
            val _start = table[s[i]]
            if (_start != null) {
                start = maxOf(start, _start + 1)
            }
            table[s[i]] = i
            answer = maxOf(answer, i - start + 1)
        }
        return answer
    }
}

Two Pointers

• O(N) time

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {   
        if (s == "") return 0
        
        // 256 ascii codes
        val table = IntArray(256) { 0 }
        // length of string
        val len = s.length
        // start pointer
        var start = 0
        var answer = 0
        // end pointer
        for (end in 0 until len) {
            // ascii code
            val code = s[end].toInt()
            // testcase1: abcabcbb
            // testcase2: baab
            start = maxOf(start, table[code])
            // store next index to exclude current position
            table[code] = end + 1
            answer = maxOf(answer, end - start + 1)
        }        
        return answer
    }
}