First, let us consider the problem without the constraints that the adjacent characters should not be chosen simultaneously.

Find the number of non-empty substring of \(S\). Here, a substring is a concatenation without reorder of the original string with 0 or more characters removed.

Here, it is important that different ways of removals may result in the same substring. We will introduce a method called “subsequence DP,” in which the substring is counted without those duplicates.

Consider the following DP.

• \(dp_i\) := The number of substrings of \(1\)-st to \(i\)-th characters of \(S\) such that \(i\)-th character is always chosen

Here, we define \(dp_0=1\), corresponding to an empty string. The transitions can be written as follows:

• \(dp_i = \sum_{j=0}^{i-1} dp_j\)

But this may count the same substring more than once, so we modify the transition as follows:

• \(dp_i=\sum_{j=k}^{i-1}dp_j\), where \(k\) is the maximum integer such that \(S_i=S_k\) and \(k<i\) (or \(k=0\) if there is no such integer)

Intuitively, if \(S_k=S_i\), then we forbid appending \(S_i\) right after \(S_j\) for some \(j(<k)\), since it does not make sense (we can append \(S_k\) after \(S_j\) instead), so that the duplicates are avoided. In fact, this is the only twist required to count all the substrings without duplicates.

At a glance, the complexity looks like \(O(|S|^2)\), but it can actually be performed in a total of \(O(|S|)\) with the aid of cumulative sums, or \(O(σ|S|)\) without them, where \(σ\) denotes the number of distinct alphabets, which is fast enough.

This idea can be applied to the original problem as well. Let \(dp_0=1\) and \(dp_1=0\). The recurrence relations can be written as:

• \(dp_{i+1}=\sum_{j=k}^{i-1}dp_j\), where \(k\) is the maximum integer such that \(S_i=S_k\) and \(k<i\) (or \(k=0\) if there is no such integer)

Sample code (C++)

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

int main(){
    string S; cin >> S;
    int N = S.size();
    vector<long long> dp(N+2); dp[0] = 1;
    for(int i = 0; i < N; i++){
        for(int j = i-1; ; j--){
            dp[i+2] = (dp[i+2] + dp[j+1]) % 1000000007;
            if(j == -1 || S[j] == S[i]) break;
        }
    }
    long long ans=0;
    for(int i = 2; i < N+2; i++) ans += dp[i];
    cout << ans%1000000007 << endl;
}