字符串专题

无重复最长子串

tip

哈希表+双指针

思路：使用一个哈希表存储字符的数量，然后用两个指针算法进行遍历判断

核心代码

string s = "abcabcbb";
int ans;
unordered_map<int,int> hash;
int l = 0, r = 0;
hash[s[0]]++;
while(l <= r and r < s.size())
{
    hash[s[++r]]++;
    while(hash[s[r]] > 1) hash[s[l++]]--;
    ans = max(ans, r - l + 1);
}

最长回文串

tip

中心扩展算法，回文串可能是偶数的也可能是奇数的。偶数和奇数需要单独进行判断

核心代码

string s = "babad";
int res = 0;
string ans;
for(int i = 0;i < s.size();i++)
{
    // 寻找以i作为中心的回文串
    for(int j = 0;i - j >= 0 and i + j < s.size();j++)
    {
        if(s[i-j] == s[i+j])
        {
            if(j * 2 - 1 > res)
            {
                res = 2 * j + 1;
                ans = s.substr(i-j,res);
            }
        }
        else break;
    }
    // 寻找以i为中心的偶数长度的回文串
    for(int j = i,k = i + 1;j >= 0 and k < s.size();j--,k++)
    {
        if(s[j] == s[k])
        {
            if(k - j + 1 > res)
            {
                res = k -j + 1;
                ans = s.substr(j,res);
            }
        }else break;
    }
}

有效括号

tip

栈 + 双指针

核心代码

string s = "(()"
stack<int> stk; // 栈存储下标
int res = 0;
// start 用来记录当前有效括号开始的坐标
// 否则栈空的时候就无法计算当前有效括号的长度了
for(int i = 0,start = -1;i < s.size();i++)
{
    if(s[i] == '(') stk.push_back(i)
    else
    {
        if(s[i].size())
        {
            stk.pop();
            if(stk.size())
                res = max(res,i - stk.top());
            else
                res = max(res,i - start);
        }
        else start = i; // 开始新一轮的匹配
    }
}

最小覆盖子串

tip

给定一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。

思路：哈希表+双指针

核心代码

string s = "ADOBECODEBANC";
string t = "ABC";
string res;
unordered_map<string,int> hs, ht;
for(auto item:t) ht[item]++;
int cnt = 0;
for(int i = 0,j = 0;i < s.size();i++)
{
    hs[s[i]]++;
    if(hs[s[i]] <= ht[s[i]]) cnt++; // 避免重复计数
    while(hs[s[j]] > ht[s[i]]) hs[s[j++]]--;
    if(cnt == t.size())
    {
        if(res.empty() and i - j + 1 < res.size())
            res = s.substr(i,i-j+1);
    }
    return res;
}