3.2 双指针

和数组类似, 双指针法也可用于字符串中.

3.2.1 问题14: 字符串中的变位词

LCR 014. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

示例 1：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

3.2.1.1 分析

变位词指的是, 对于字符串s, 其变位词的字母和出现次数和s相同, 而出现顺序不同. (acb, bca 就是abc的变位词之一).

对于 s1 的变位词, 其出现字母和次数都是相同的, 那么可以用 (k, v) 为 (字母, 出现次数) 的哈希表 cnt 来表示 s1 及其变位词.

要判断 s1及其变为词是否为 s2 的子串:

1. 扫描s1, 将 cnt 对应的字母次数减1, 此时cnt之和必然小于0 (s1 在 cnt 中的字符次数之和为 -len(s1))
2. 扫描s2, 使用双指针 left, right 表示子串区间 (目标是移动子串区间, 使得区间在 cnt 中出现的次数之和为len(s1), 也就是整体的cnt之和为0):
   1. 若 s2[right] 字符x出现次数大于0, 则 left 右移, 减少字符, 那么 cnt 之和必然减少1; 持续右移 left, 直到 cnt[x] 之和不大于0
   2. 若此时, 子串长度等于 s1 的长度, 那么 cnt 之和必然为0, 即 s1 为 s2 的子串

3.2.1.2 题解

1. 扫描 s1, 记录字符出现次数(次数减一)
2. 扫描 s2, 对于子区间[left, right]:
   1. right 处字符x 出现次数加一
   2. 若次数 cnt[x] 大于0, 那么减小区间(left 右移), cnt[s2[left]] 减一, 直到cnt[x] 不大于0为止
   3. 此时cnt之和一定是不大于0的, 若此时区间长度刚好为 len(s1), 那么此时 cnt之和一定为0, s1为s2的子串

时间复杂度: $O(n+m)$ 扫描 s1 和 s2

空间复杂度: O(1), 使用的哈希表长度为定值

func checkInclusion(s1, s2 string) bool {
	// 判断特殊情况
	if len(s2) < len(s1) {
		return false
	}

	// 哈希表, 字符: 次数
	cnt := make([]int, 26)

	// 扫描 s1, 次数值减一
	for _, c := range s1 {
		cnt[c-'a']--
	}

	// 扫描 s2, 移动子区间
	left := 0
	for right, c := range s2 {
		x := c - 'a'
		cnt[x]++
		// 次数大于0, 减小区间
		for cnt[x] > 0 {
			cnt[s2[left]-'a']--
			left++
		}
		// 此时 cnt 之和一定是不大于0的
		// 若区间长度和s1相同, 那么cnt之和一定为0
		if right-left+1 == len(s1) {
			return true
		}
	}

	return false
}

3.2.2 问题15: 字符串中所有的变位词

LCR 015. 找到字符串中所有字母异位词

输入字符串s1和s2, 输出s2的所有变位词在字符串s1中的下标.

假设只包含小写字母.

示例 1：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。

示例 2：

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

3.2.2.1 分析

思路和判断变位词相同, 对于s1的子串区间[le, ri], 若子串是s2的变位词, 那么le即位其下标.

3.2.2.2 题解

时间复杂度: O(n)

空间复杂度: O(1)

func findAnagrams(s, p string) []int {
	// 判断边界
	if len(s) < len(p) {
		return []int{}
	}

	result := make([]int, 0)
	// 哈希表, 字符:次数
	cnt := make([]int, 26)

	// 扫描 p
	for _, c := range p {
		cnt[c-'a']--
	}

	// 扫描 s, 移动子区间
	left := 0
	for right, c := range s {
		x := c - 'a'
		cnt[x]++
		// 右移左指针, 直到cnt[x]不大于0
		for cnt[x] > 0 {
			cnt[s[left]-'a']--
			left++
		}
		// 当子区间长度等于p长度时, 满足p及其变位词为s的子串
		if right-left+1 == len(p) {
			result = append(result, left)
		}
	}

	return result
}

3.2.3 问题16: 不含重复字符的最长字符串

LCR 016. 无重复字符的最长子串

输入字符串, 求字符串中不含重复字符的最长子串的长度.

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: s = ""
输出: 0

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

3.2.3.1 分析

构建哈希表(字符:出现次数), 若字符串不包含重复字符, 那么哈希表中的值一定不会大于1.

由于字符串由英文字母、数字、符号和空格组成, 那么哈希表长度为ASCII码个数 256.

使用双指针来表示子字符串:

1. 若当前区间满足条件, 右指针右移(增加字符), 继续判断
2. 若当前区间不满足条件, 左指针右移(减少字符), 继续判断
3. 找出满足条件的最大长度

3.2.3.2 题解

多次遍历哈希表

1. 若为空字符串, 返回0
2. 构建长度为 256 的哈希表
3. 扫描字符串, 对于子串区间:
   1. 区间包含重复字符, 减小区间(删除字符), 直到不包含为止
   2. 区间不包含重复字符, 更新最大长度

时间复杂度: O(n), 但是判断是否包含重复字符需要多次遍历哈希表, 当哈希表较大时增大开销.

package ordastring

func lengthOfLongestSubstring(s string) int {
    maxLen := 0

    // 边界值
    if len(s) == 0 {
       return maxLen
    }

    // 哈希表, 字符:次数, ASCII共256个
    cnt := make([]int, 256)

    // 扫描 s, 移动子区间
    left := 0
    for right, c := range s {
       cnt[c]++
       // 包含重复字符则减小区间
       for hasGreaterThan1(cnt) {
          // 移除字符
          cnt[s[left]]--
          left++
       }
       // 更新最大长度
       maxLen = max(maxLen, right-left+1)
    }

    return maxLen
}

func hasGreaterThan1(cnt []int) bool {
    for _, n := range cnt {
       if n > 1 {
          return true
       }
    }

    return false
}

func max(a, b int) int {
    if a > b {
       return a
    }
    return b
}

使用缓存避免遍历哈希表

使用变量 cntDup 来缓存重复字符的情况.

对于子区间, 若右指针右移(新增一个字符), 若此时cnt[c] > 1表示出现重复字符, 则:

1. 左指针右移(删除字符), 判断删除后是否还存在重复字符, 存在则继续减小区间, 直到不存在重复字符为止

此方法避免多次遍历哈希表, 效率有所提升

func lengthOfLongestSubstringWithCountDup(s string) int {
    maxLen := 0

    // 边界值
    if len(s) == 0 {
       return maxLen
    }

    // 哈希表, 字符:次数
    cnt := make([]int, 256)

    // 扫描s, 移动子区间
    left := 0
    cntDup := 0 // 标记是否存在重复字符
    for right, c := range s {
       cnt[c]++
       if cnt[c] > 1 {
          cntDup++
       }
       // 存在重复字符,减小区间
       for cntDup > 0 {
          // 删除字符
          cnt[s[left]]--
          // 下个区间是否存在重复字符
          if cnt[s[left]] == 1 {
             cntDup--
          }
          left++
       }

       maxLen = max(maxLen, right-left+1)
    }

    return maxLen
}

3.2.4 问题17: 包含所有字符的最短字符串

LCR 017. 最小覆盖子串

输入字符串s和t, 找出字符串s中包含t中所有字符的最短子串.

若不存在, 返回空字符串; 若存在多个, 返回任意一个.

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母组成

**进阶：**你能设计一个在 o(n) 时间内解决此问题的算法吗？

3.2.4.1 分析

构建长度为 52 的哈希表(字符:次数).

扫描字符串t, 将出现的字符次数加一.

扫描字符串s, 对于子区间:

1. 缓存t中存在但是s中不存在的字符个数 (count). count == 0 时表示区间包含所有t的字符
2. 字符次数减一, 判断是否包含t中所有字符. 若不包含则增加区间, 直到包含为止

3.2.4.2 题解

import "math"

func minWindow(s string, t string) string {
    minStr := ""

    // 边界
    if len(s) < len(t) {
       return minStr
    }

    // 构建哈希表, 字符:次数, 长度为英文字符个数
    m := make(map[byte]int, 52)

    // 扫描 t
    for i := range t {
       m[t[i]]++
    }

    // 扫描 s, 移动子区间
    left, right := 0, 0       // 当前子区间
    minLen := math.MaxInt     // 最小子串长度
    minLeft, minRight := 0, 0 // 最小子串区间
    count := len(m)           // 区间中未包含的t中字符的个数

    // 边界值: 右指针已经到达末尾, 此时刚好包含所有的t中字符
    // 需要进行最后一次计算
    for right < len(s) || (count == 0 && right == len(s)) {
       // 存在未包含的t中字符, 需要扩大区间
       if count > 0 {
          // 包含t中字符
          if _, ok := m[s[right]]; ok {
             // 减少次数
             m[s[right]]--
             // 已包含全部的当前字符
             if m[s[right]] == 0 {
                count--
             }
          }
          // 增大区间
          right++
       } else { // 已包含所有的t中字符, 减小区间
          // 记录最小区间
          // s[l, r] 长度为 r-l
          if (right - left) < minLen {
             minLen = right - left
             minLeft = left
             minRight = right
          }

          if _, ok := m[s[left]]; ok {
             // 增加次数
             m[s[left]]++
             // 存在不包含的t中字符
             if m[s[left]] == 1 {
                count++
             }
          }
          // 减小区间
          left++
       }
    }

    // 存在
    if minLen < math.MaxInt {
       return s[minLeft:minRight]
    }
    return ""
}

Reference

1. 剑指Offer（专项突破版）