在Kotlin中回答最长的子字符串而不重复字符

Question

我花了一些时间在这个问题上，并得到了这个接近

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
}

我理解需要一个HashSet来回答这个问题，因为它不允许重复字符，但我一直得到类型不匹配错误。我并非不犯错。如有任何协助，不胜感激。

Answer 1

你的误解是r代表字符串中的一个字符，而不是字符串的索引，所以说s[r]没有意义。你指的是r。

但是您也单独使用r，因此您应该使用forEachIndexed，它允许您访问序列的元素和该元素的索引:

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

}

尽管你的代码中仍然有一些部分不太有意义。

while(!set.add(r)) set.remove(r)在功能上与set.add(r)相同。如果add返回false，则表示该元素已经在集合中，则删除该元素，下一次循环将该元素添加回集合中。如果add返回true，则表示集合中不存在该元素，并且成功添加了该元素，因此无论如何，结果都是将r添加到集合中。

然后你又做了set.add(r)两行之后出于某种原因?

无论如何，这里有一个蛮力解决方案，你可以用它作为优化的起点:

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