CF Blogs | Permutations on String | Number of Strings with no K consequetive equal letters

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Permuation Question : Number of Strings with no K consequetive equal letters given the string is made of lower case alphabets

Read here : Explanation It has beautiful solution using recurrence formulaes.

Basically the Recurrence is :
if k == n:    ways[n] = (power(26,k) - 26)
if n <= k - 1:   ways[n] = power(26,n)
else ways[n] = (countValid(n-1,k) + countValid(n-k,k))

You need to take care of modular arithmetic of course as the numbers get really large BTW it was there in Atlassain OA — best OA ever

C++

int64_t modularPower(int64_t b , int64_t e ) {
	
	int64_t MOD = 1e9 + 7;
	
    if ( MOD == 1) return 0; // Handling edge case

    int64_t r = 1;
    
    b = b % MOD;

    while (e > 0) {
        // If exponent is odd, multiply base with result
        if ( e % 2 == 1) {
            r = (r * b) % MOD;
        }

        // exponent must be even now
        e = e >> 1; // Equivalent to exponent /= 2
        b = (b * b) % MOD;
    }

    return r;
}

const int64_t MOD = 1e9 + 7;
void solve()
{
    int64_t N , K ;
    
    cin >> N >> K ;
    
    vector<int64_t> dp(N+1,-1);
    
    function< int64_t (int64_t)> dfs = [&]( int64_t n )
    {
    	if( dp[n] != -1 )
    	{
    		return dp[n];
    	}
    	
    	if( n == K ) return dp[n] = ( modularPower( 26 , K  ) - 26 );

    	if( n <= K - 1 ) return dp[n] =  modularPower( 26 , n); 
    	
    	if( dp[n-1] != -1 && dp[n-K] != -1  )
    	{
    		return dp[n] = dp[n-1] + dp[n-K];
    	}
    	else
    	{
    		return dp[n] = dfs( n-1 ) + dfs( n - K );
    	}
    };
    
    for( int i = 1 ; i < K ; i++ )
    {
    	dp[i] = modularPower( 26 , i ); 
    	dp[i] %= MOD ;
    } 
    
    dp[K] = modularPower( 26 , K  ) - 26;
    
    dp[K] %= MOD ;
    
    for( int i = K + 1 ; i <= N ; i++ )
    {
    	dp[i] = (dp[i-1] % MOD + dp[i-K] % MOD) % MOD  ;
    	dp[i] %= MOD ;
    }
    
    cout << dp[N] << endl;
    	
    
    
    cout << dfs( N ) << endl;
    
}


signed main()
{
    fastio;
    int t=1;
    cin >> t ;
    while(t--) solve();
    return 0;
}

python

import math
from functools import lru_cache

# Initialize a dictionary to store computed results
dp = [-1] * 100005 
def power(a, k, p = 10**9 + 7):
    res = 1
    a = a % p
    while k > 0:
        if k % 2 == 1:
            res = (res * a) % p
        k = k // 2
        a = (a * a) % p
    return res

def countValid(n, k):
    MOD = 10**9 + 7

    if dp[n] != -1:
        return dp[n]
    
    if k == n: 
        dp[n] = (power(26,k) - 26) % MOD
        return dp[n]
    
    if n <= k - 1:
        dp[n] = power(26,n)% MOD
        return dp[n]
    
    if dp[n-k] != -1 and dp[n-1] != -1:
        dp[n] = (dp[n-1]%MOD + dp[n-k]%MOD)%MOD
    else:
        dp[n] = (countValid(n-1,k)% MOD + countValid(n-k,k)% MOD)% MOD
    
    return dp[n]

countValid(1000,10)

Comments (5)

Write comment?

samadeep

14 months ago, # |

WHy the downvote my friends ?

→ Reply

__StoneHeart

I upvoted.

14 months ago, # ^ |

Thanks bro

longrange

is this blog really necessary?

← Rev. 2 →

Its actually something i found interesting as a problem for understanding why permutations and combinations using binomial coefficients are slower than recursive techniques

Ofcourse on necessity i have no comments its just that i found this interesting Any criticism is welcome.

samadeep's blog