Skip to content

1020 Delete At Most Two Characters

Statement

Metadata

  • 作者: CAO, Peng
  • 单位: Google
  • 代码长度限制: 16 KB
  • 时间限制: 200 ms
  • 内存限制: 64 MB

Given a string which contains only lower case English letters, how many different strings you can get after deleting AT MOST TWO characters in it?

Input Specification

Each input file contains one test case, which gives the string whose length is in [3, 10^6].

Output Specification

Print in a line the number of different strings you can get after deleting at most 2 characters.

Sample Input 

ababcc

Sample Output 

15

Hint

Deleting 0 character gets ababcc.

Deleting 1 character gets babcc, aabcc, abbcc, abacc and ababc.

Deleting 2 character gets abcc, bbcc, bacc, babc, aacc, aabc, abbc, abac and abab.

Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000010
int n;
char s[N];
int pos[220];
ll f[N][4];
int main() {
    while (scanf("%s", s + 1) != EOF) {
        memset(pos, -1, sizeof pos);
        n = strlen(s + 1);
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            int d = pos[s[i]];
            pos[s[i]] = i;
            f[i][0] = f[i][1] = 1;
            for (int j = 1; j < 4; ++j) {
                f[i][j] += f[i - 1][j];
                f[i][j + 1] = f[i - 1][j];
                if (d != -1 && j - i + d >= 0)
                    f[i][j] -= f[d - 1][j - i + d];
            }
        }
        printf("%lld\n", f[n][0] + f[n][1] + f[n][2]);
    }
    return 0;
}
Last update: May 4, 2022
Back to top