Answering the Longest Substring Without Repeating Characters in Kotlin

user_14243745 0
Viewed 63

I've spend some time working on the problem and got this close

 fun lengthOfLongestSubstring(s: String): Int {
        var set = HashSet<Char>()
        var initalChar = 0
        var count = 0
        
        s.forEach {r ->
            while(!set.add(s[r]))
            set.remove(s[r])
            initalChar++
            set.add(s[r])
            count = maxOf(count, r - initialChar + 1)
            
        }
        return count
    }

I understand that a HashSet is needed to answer the question since it doesn't allow for repeating characters but I keep getting a type mismatch error. I'm not above being wrong. Any assistance will be appreciated.

kotlin data-structures hashset algorithm
1 Answers

Your misunderstanding is that r represents a character in the string, not an index of the string, so saying s[r] doesn't make sense. You just mean r.

But you are also using r on its own, so you should be using forEachIndexed, which lets you access both the element of the sequence and the index of that element:

s.forEach { i, r ->
    while(!set.add(r))
        set.remove(r)
    initialChar++
    set.add(r)
    count = maxOf(count, i - initialChar + 1)
    
}

Though there are still some parts of your code that doesn't quite make sense.

while(!set.add(r)) set.remove(r) is functionally the same as set.add(r). If add returns false, that means the element is already in the set, you remove it and the next iteration of the loop adds the element back into the set. If add returns true, that means the set didn't have the element and it was successfully added, so in any case, the result is you add r to the set.

And then you do set.add(r) again two lines later for some reason?

Anyway, here is a brute-force solution that you can use as a starting point to optimise:

fun lengthOfLongestSubstring(s: String): Int {
    val set = mutableSetOf<Char>()
    var currentMax = 0
    // for each substring starting at index i...
    for (i in s.indices) {
        // update the current max from the previous iterations...
        currentMax = maxOf(currentMax, set.size)
        // clear the set to record a new substring
        set.clear()

        // loop through the characters in this substring
        for (j in i..s.lastIndex) {
            if (!set.add(s[j])) { // if the letter already exists
                break // go to the next iteration of the outer for loop
            }
        }
    }
    return maxOf(currentMax, set.size)
}
user_51335850
Related