最长子串

常用 Map 记录上一个在哪/有没有/有多少

Map 可以用 array 实现

最长子串

3. 无重复字符的最长子串 mid

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

给定一个字符串 s, 请你找出其中不含有重复字符的最长子串的长度。
Given a string s, find the length of the longest substring without repeating characters.

记一下 char 上次出现的 idx; 如果 lastIdx >= start, 更新 start, 否则更新 len

javago

java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[128];
        Arrays.fill(map, -1);
        char[] arr = s.toCharArray();
        int res = 0;
        int start = 0;
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            int lastIdx = map[c];
            if (lastIdx >= start)
                start = lastIdx + 1;
            else
                res = Math.max(res, i - start + 1);
            map[c] = i;
        }
        return res;
    }
}

func lengthOfLongestSubstring(s string) int {
    m := map[rune]int{}
    start := 0
    res := 0
    for i, c := range s {
        lastIdx, has := m[c]
        if has && lastIdx >= start {
            start = lastIdx + 1
        } else {
            res = max(res, i-start+1)
        }
        m[c] = i
    }
    return res
}
func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

5. 最长回文子串 mid

给你一个字符串 s，找到 s 中最长的回文子串。
Given a string s, return the longest palindromic substring in s.

解法 1 中心扩散

从头到尾遍历, 每次迭代中向两端扩展, 并更新最长
有指针会很方便

javago

java

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2)
            return s;

        char[] chs = s.toCharArray();
        int[] endPoint = new int[] { 0, 0 };
        for (int i = 0; i < chs.length - 1; i++) {
            extendAndJudge(chs, i, 0, endPoint);
            extendAndJudge(chs, i, 1, endPoint);
        }
        return s.substring(endPoint[0], endPoint[1] + 1);
    }

    private void extendAndJudge(char[] arr, int idx, int offset, int[] endPoint) {
        int l = idx, r = idx + offset;
        while (l >= 0 && r < arr.length) {
            if (arr[l] != arr[r])
                break;
            l--;
            r++;
        }
        l++;
        r--;
        if (r - l > endPoint[1] - endPoint[0]) {
            endPoint[0] = l;
            endPoint[1] = r;
        }
    }
}

func longestPalindrome(s string) string {
    n := len(s)
    var r1, r2 int = 0, 0
    for i := 0; i < n-1; i++ {
        extend(s, i, 0, &r1, &r2)
        extend(s, i, 1, &r1, &r2)
    }
    return s[r1 : r2+1]
}

func extend(s string, idx int, offset int, l *int, r *int) {
    i, j := idx, idx+offset
    n := len(s)
    for i >= 0 && j < n {
        if s[i] != s[j] {
            break
        }
        i--
        j++
    }
    // 回退
    i++
    j--
    if *r-*l < j-i {
        *l = i
        *r = j
    }
}

解法 2 manacher

manacher 是一个精准且有技巧性的算法, 我们用尽可能少的描述讲清楚它
整体而言, manacher 是根据对称性减少计算复杂度, 有点状态转移的味道

首先, 回文串因中心元素数量可能为 1 个或 2 个, 存在差异; 那么, 向元素之间插入相同的字符 char, 这样构造出来的新字符串就避免了这种差异
另外, 为方便, 在新构造的字符串左右两侧分别加入 1 个不同的字符 ^, $ 作为栅栏
不妨设构造后的任意回文串 $S_{i}$ 的中心元素的索引为 i, 回文串的半径(不包含中心元素)为臂展

然后, 计算每个位置的臂展, 并存入数组 arm[] 中
要计算臂展, 最朴素的方式就是从中心向两侧扩散, 不过有一些技巧性的方式简化
我们从左往右计算每个位置的臂展, 如果当前位置 i 仍然在一个回文串 $S_{c o r e}$ (中心元素位置为 core)的覆盖下, 那么, 当前位置 i 跟 j=(2*core-i) 是关于 core 对称点;
如果回文串 $S_{j}$ 完全被 $S_{c o r e}$ 覆盖, 可以直接获取到中心为 i 的回文串 $S_{i}$ , 两个回文串是镜像

core 是 $S_{c o r e}$ 右臂 right 取最大时的位置:
$c o r e = \underset{i d x}{\arg max (r i g h t)}$

但是要考虑一些特殊情况:
$S_{c o r e}$ 没有覆盖 i
$S_{j}$ 没有完全被 $S_{c o r e}$ 覆盖, 也就是说 $S_{j}$ 的左臂超出了 $S_{c o r e}$ 的覆盖范围
$S_{j}$ 因为受到左端点的限制, 臂展很小

这些情况下, 需要用朴素的方式向两端扩展求出臂展; 但是不需要写到 if-else 里

在插入 char 之后, 有了一些性质:
原回文串长度 = 臂展长度
例如: len("#1#1#") = 2, len("#1#") = 1
原左端点 = 新左端点/2 = (i-新臂展)/2
例如: 新构造的左侧为 ^#1#, 原左端点 = 新的左端点/2 = (i-新臂展)/2 = (2-1)/2 = 0,

在求得所有臂展后, 找到最大臂展, 根据上述性质求得最长回文串

java

class Solution {
    public String longestPalindrome(String s) {
        if (s.isEmpty()) return s;
        char[] arr = preProcess(s);
        int n = arr.length;
        int[] arm = new int[n];
        int core = 0, right = 0; // core 是 right 取到 max 时的 idx
        // 遍历 i 的过程中, 维护 core 和 right
        for (int i = 1; i < n - 1; i++) {
            // j 是 i 关于 core 的对称点
            int j = 2 * core - i;
            // 先转移一下状态
            if (i < right) {
                arm[i] = Math.min(right - i, arm[j]); // 如果j的左臂超过了left, i的右臂先伸展到right
            }
            // 尝试向两边扩, 原因如下:
            // 1.i超过了right 2.i的右臂超过了right 3.j的左臂因arr[0]受限
            while (arr[i + arm[i] + 1] == arr[i - arm[i] - 1]) {
                arm[i]++;
            }

            // 更新 right
            if (i + arm[i] > right) {
                core = i;
                right = i + arm[i];
            }
        }
        // 找到最大臂展, 求得左右端点
        int idx = 0;
        int len = 0;
        for (int i = 1; i < n - 1; i++) {
            if (arm[i] > len) {
                len = arm[i];
                idx = i;
            }
        }
        // 原左端点==(i-臂展)/2
        // 原最大长度==臂展长度
        int start = (idx - len) / 2;
        return s.substring(start, start + len);
    }

    /**
     * 预处理
     */
    private char[] preProcess(String s) {
        StringBuilder sb = new StringBuilder("^#");
        for (char c : s.toCharArray()) {
            sb.append(c).append("#");
        }
        sb.append("$");
        return sb.toString().toCharArray();
    }
}

32. 最长有效括号 hard

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

解法 1 栈

栈中会存入 '(', 那么随着 '(' 的 pop, 会不知道起始位置; 此时栈底部存一个 ')' 就能知道起始位置在哪了
栈底存储没有被匹配的 ')' 索引作为分隔, 栈中存储 '(' 索引

javapythonc++

java

class Solution {
    public int longestValidParentheses(String s) {
        char[] arr = s.toCharArray();
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                stack.push(i);
                continue;
            }
            stack.pop();
            // 空栈代表栈底的分隔符pop了
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                res = Math.max(res, i - stack.element());
            }
        }
        return res;
    }
}

python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res = 0
        stack = list()
        stack.append(-1)
        for i, e in enumerate(s):
            if e == '(':
                stack.append(i)
                continue
            stack.pop()
            if len(stack) == 0:
                stack.append(i)
            else:
                res = max(res, i - stack[len(stack) - 1])

        return res

c++

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stk.push(i);
                continue;
            }
            stk.pop();
            if (stk.empty()) stk.push(i);
            else res = std::max(res, i - stk.top());
        }
        return res;
    }
};

解法 2 DP

dp 保存以 i 为结束的子串的最大长度
个人认为这种算法不优雅, 只有 dp 狂人才会这样做

java

public class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        char[] arr = s.toCharArray();
        // 以 i 为结尾的长度
        int[] dp = new int[arr.length];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == '(') continue;
            if (arr[i - 1] == '(') {
                dp[i] = 2 + (i >= 2 ? dp[i - 2] : 0);
            } else {
                // 注意的索引计算
                int startIdx = i - 1 - dp[i - 1];
                if (startIdx >= 0 && arr[startIdx] == '(') {
                    // 连起来
                    dp[i] = 2
                            + dp[i - 1]
                            + (startIdx >= 1 ? dp[startIdx - 1] : 0);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

解法 3 计数

从左到右计数, ')' 数量多则归零, 数量相等则计算 max;
为解决 "(()" 这种情况, 再从右向左统计, 取 2 次统计的最大值;

javapyc++

java

class Solution {
    public int longestValidParentheses(String s) {
        int l = 0, r = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') l++;
            else r++;
            if (l == r) max = Math.max(max, 2 * r);
            else if (r > l) l = r = 0;
        }
        l = r = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') l++;
            else r++;
            if (l == r) max = Math.max(max, 2 * l);
            else if (l > r) l = r = 0;
        }
        return max;
    }
}

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        m, l, r = 0, 0, 0
        for e in s:
            if e == '(':
                l += 1
            else:
                r += 1
            if l == r:
                m = max(m, 2 * l)
            elif r > l:
                l = r = 0

        l = r = 0
        i = len(s) - 1
        while i >= 0:
            if s[i] == '(':
                l += 1
            else:
                r += 1
            if r == l:
                m = max(m, 2 * r)
            elif l > r:
                l = r = 0
            i -= 1

        return m

c++

class Solution {
public:
    int longestValidParentheses(string s) {
        int l = 0, r = 0, res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') l++;
            else r++;
            if (l == r) res = std::max(res, 2 * r);
            else if (r > l) l = r = 0;
        }
        l = r = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '(') l++;
            else r++;
            if (l == r) res = std::max(res, 2 * l);
            else if (l > r) l = r = 0;
        }
        return res;
    }
};

485. 最大连续 1 的个数 easy

给定一个二进制数组 nums ，计算其中最大连续 1 的个数。

java

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0, cnt = 0;
        for (int x : nums) {
            if (x != 1) cnt = 0;
            else cnt++;
            max = Math.max(max, cnt);
        }
        return max;
    }
}

最长子串 ​

最长子串 ​

3. 无重复字符的最长子串 mid ​

5. 最长回文子串 mid ​

32. 最长有效括号 hard ​

485. 最大连续 1 的个数 easy ​

最长子串

最长子串

3. 无重复字符的最长子串 mid

5. 最长回文子串 mid

32. 最长有效括号 hard

485. 最大连续 1 的个数 easy