3. Longest Substring Without Repeating Characters

[yunshuipiao]

3. Longest Substring Without Repeating Characters

[TOC]

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

Example 1:

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

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

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

解法一：使用额外列表保存中间结果

遍历字符串，求出以当前字符为终点的满足条件的字符串，与当前结果比较，取最大者。

代码如下：

/**
 * 注意空格, 空格也算一个字符
 * 空间复杂度 O(n), 时间复杂度O(n*n)
 */
fun lengthOfLongestSubstring(s: String): Int {
    var result = 0
    if (s.isEmpty()) {
        return 0
    }
    val l = arrayListOf<Char>()
    for (index in 0 until s.length) {
        l.clear()
        for (i in index downTo 0) {
            val findIndex = l.indexOf(s[i])
          	// 没找到重复字符串
            if (findIndex != -1) {
                break
            } else {
                l.add(0, s[i])
            }
        }
        if (l.size > result) {
            result = l.size
        }
    }
    return result
}

解法二： 优化

使用一个 tempStr 来保存当前最长的无重复子串，比第一种解法更容易理解.

/**
 * 注意空格
 * 空间复杂度 O(n), 时间复杂度O(n*n)
 */
fun lengthOfLongestSubstring(s: String): Int {
    var result = 0
    var tempStr = ""
    for (index in 0 until s.length) {
        val i = tempStr.indexOf(s[index])
        if (i != -1) {
            // 当前中有重复元素
            tempStr = tempStr.substring(i + 1) + s[index]
        } else {
            tempStr += s[index]
        }
        result = Math.max(tempStr.length, result)

    }
    return result
}