LeetCode3.滑动窗口: 双指针法(Kotlin语言)-无重复字符的最长子串

题目描述

无重复字符的最长子串

• 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

暴力破解法

/**
 * 暴力破解法: 遍历所有子串,会出现超时 LTE
 */
fun lengthOfLongestSubstring(s: String): Int {
    var ans = 0
    // 遍历所有子串
    val charArray = s.toCharArray()
    val n = charArray.size
    if (n == 0) return 0
    for (i in 0 until n) {
        for (j in i..n) {
            val substr = s.substring(i, j)
            if (isUniqString(substr)) {
                ans = Math.max(ans, substr.length)
            }
        }
    }
    return ans
}

/**
 * 判断字符串中的字符是否全部无重复
 */
fun isUniqString(s: String): Boolean {
    val charArray = s.toCharArray()
    val len1 = charArray.size
    val len2 = charArray.groupBy { it }.keys.size
    return len1 == len2
}

滑动窗口: 双指针法

滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j) 向右滑动 1 个元素，则它将变为 [i+1, j+1) (左闭，右开）。

使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。

回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。
然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。

此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。
如果我们对所有的 i 这样做，就可以得到答案。

滑动窗口-双指针法源代码

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        var ans = 0
        var left = 0
        var right = 0
        val n = s.length

        val window = mutableSetOf<Char>()

        while (left < n && right < n) {
            // slide right pointer
            if (!window.contains(s[right])) {
                window.add(s[right++])
                ans = Math.max(ans, right - left)
            } else {
                // slide left pointer
                window.remove(s[left++])
            }
        }

        return ans
    }

}

3. Longest Substring Without Repeating Characters

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.

参考资料

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

---

Kotlin 开发者社区

国内第一Kotlin 开发者社区公众号，主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界，越需要宁静的思考。