# TACNTSTR - editorial

Author: Tuấn Anh Trần Đặng
Tester: Kamil Dębowski
Editorialist: Tuấn Anh Trần Đặng

Medium

### PREREQUISITES:

Dynamic Programming

# Problem

Given the string S count the number of the strings of same length T such that T is lexicographically bigger then S and when we reverse the order of characters in both of the two strings T is still lexicographically bigger than S.

# Solution

We will using dynamic programing (dp). Let F[i][ok1][ok2] is the number of the strings T that we can generated if we already got the first i-1 characters of it and ok1 and ok2 represent the following information:

• ok1 = 0 mean the first i - 1 characters of T still match the corresponding t - 1 characters of S. ok1 = 1 mean T is larger then S.
• ok2 = 0 mean in the reversed order the first t - 1 characters in T is already lexicographically larger then the corresponding characters in S. ok2 = 0 if otherwise.

Let N is the length of S The result of course will be F. We can initialize the dp with FN + 11 = 1. We will calculate F in the decreasing order of i. With each i, ok1, ok2, we try to put all possible character in position i so that T is never lexicographically smaller than S in the original order:

//let s is 0-indexed
for (int i = N - 1; i > 0; i--)
for (int ok1 = 0; ok1 <= 1; ok1++)
for (int ok2 = 0; ok2 <= 1; ok2++) {
//make sure that T is always lexicographically larger than S in original order
for (char c = ok1 == 0 ? s[i] : 'A'; c <= 'Z'; c++) {
int nextOk2 = ok2;
if (c != s[pos]) {
//if we put a character c > s[pos] in position pos of T then T became lexicographically larger than S in reversed order
nextOk2 = c > s[pos];
}

f[pos][ok1][ok2] = (f[pos][ok1][ok2] + f[pos + 1][ok1 || c > s[pos]][nextOk2]) % MOD;
}
}



The complexity will be O(N × 2 × 2 × 26)

### Author’s/Tester’s Solutions:

2 Likes

O(N)

3 Likes

Solution in O(2*N)

2 Likes

Alternate Approach :

Define F(i) to be number of valid strings T which have i as the last position where it differs from S .

And G(i) be number of strings of length i which are >= prefix of S (prefix till i).

Then ,

Let X = S[i]-A

F(i) = G(i-1)*(25-X) and G(i) = G(i-1)*26-X+1 .

\sum_{i=0}^{n-1} F(i) is what we need .

7 Likes

Typo :
"ok2 = 0 mean in the reversed order the first t - 1 characters in T is already lexicographically larger then the corresponding characters in S. ok2 = 0 if otherwise. " It should be ok2 = 1 in one of the two places .

2 Likes

is it correct " F(i) to be number of valid strings T which have i as the last position where it differs from S, and greater than S(till ‘i’) " ?

Editorials should be more pictorial. Since, visualizing things like dp makes it more clear.

why this problem is not available for the practice.
when i am trying to open practice link getting message “Problem is not visible now. Please try again later.”

G(i)=G(i-1)*26-X only !!

Try that and you will get a WA 1 Like

what is wrong with this approach:

MOD = 10^9 + 7;

num = 1;

for i from 0 to n

  num = (num * (91 - string[i]))%MOD;


endfor

num = num - 1;

print num