SWEGSTR - Editorial

PROBLEM LINK:

Contest
Practice

Authors: Sahil Grover
Testers: Vaibhav Daga
Editorialist: Sahil Grover

DIFFICULTY:

Easy

PREREQUISITES:

Basic math, Sweg

PROBLEM:

We need to find the number of strings of length N made by using at most K alphabets such that every substring of length exactly equal to M is a palindrome.

EXPLANATION:

In this problem we have to consider 5 cases:
if M > N : No substring of length M is possible in a string of length N so we simply print “Sweg”(without quotes).
if M = 1 : Any string of length N is possible so the answer is K^N.
if M = N : The string itself must be a palindrome. So the answer will be K^((N+1)/2) (’/’ implies integer division).
if 1 < M < N :
if M is odd, the answer will be K^2.
if M is even, the answer will be K.
The answer can be evaluated using Recursive Modular Exponentiation.

Time Complexity:

Worst case time complexity for each test case will be O(log N) (when M = 1 ).

AUTHOR’S SOLUTION:

Author’s solution can be found here

3 Likes
//