E29950: 稳定的符文序列

two pointers, http://cs101.openjudge.cn/practice/E29950

#include <iostream>
#include <vector>

auto main() -> int {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  std::string s;
  std::cin >> s;
  int maxLen = 0;
  int left = 0;
  std::vector<int> last(26, -1);
  for (int right = 0; right < s.length(); ++right) {
    int char_idx = s[right] - 'a';
    if (last[char_idx] >= left)
      left = last[char_idx] + 1;

    last[char_idx] = right;
    maxLen = std::max(maxLen, right - left + 1);
  }

  std::cout << maxLen << '\n';
  return 0;
}

共用时20min

思路：双指针, 遇到重复字母, 就不断右移左指针, 直到弹出那个重复字母, 用 mask 的二进制第 i 记录第 i 个字母是否出现

#include <bits/stdc++.h>
using namespace std;

int get(char c) {
	return (1 << (c - 'a'));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int l = 0, r = 0;
    int max_len = 0, mask = 0;
    while (r < s.length()) {
    	if ((get(s[r]) & mask)) {
    		while (s[l] != s[r]) {
				mask -= get(s[l]);
				l++;
			}
			mask -= get(s[l]);
			l++;
		}
		mask += get(s[r]);
    	max_len = max(max_len, r - l + 1);
    	r++;
	}
	cout << max_len << '\n';
	return 0;
}