# Special String

Posted: 26 Nov, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note:

``````It is guaranteed that the input string is special.
``````
##### Input Format:
``````The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case will contain two integers ‘N’ and ‘P’ that denote the size of the string ‘S’ and the first letters of English alphabets used.

The second line of each test case will contain the string ‘S’ and String ‘S’ contains only lowercase letters i.e [a-z].
``````
##### Output Format:
``````For each test case, you have to return a string if there is any string that is lexicographically larger than ‘S’ and also it must be special. If there is no such string of length ‘N’ then return “NO”.

Output for every test case will be printed in a separate line.
``````
##### Note:
``````You don’t need to print anything; It has already been taken care of.
``````
##### Constraints:
``````1 <= T <= 10^2
1 <= N <= 10^3
1 <= P <= 26
1 <= |S| <= 10^3

Time Limit: 1 sec
`````` Approach 1

Intuition: As we know that the string given to us will be a special string, which means that the given string doesn’t have a palindrome substring of length 2 or more. Thus, we will try to use it and change the characters of the string as per the requirement. Every time when there is a palindrome string of size greater than 2, it always has a substring of size 2 or 3 which will also be a palindrome. Thus, if we don’t have a palindrome substring of size 2 or 3 then we can say that the entire string doesn’t have any palindrome substring of size greater than 2. Thus, the string is special.

Approach: The basic idea of this approach is to find a proper character from last. If there is no such character then try to find an element present on the left of it. We will run it until we get a particular position that has the next character which can form a special string. If we reach in front of the string and do not find it even then, we will return “NO” and can say that no string of ‘N’ is present which is lexicographically larger than ‘S’ and is a special string.

Here is the algorithm:

specialString(S, N, P):

1. Initialize a vector ‘ARR’ of size ‘N + 1’ and assign them values as the letter on that particular position.
2. If ‘helper(ARR, N, P)’ is equal to false:
• Then convert the entire ‘ARR’ into a string with the help of a temporary string ‘ANS’ and return ‘ANS’.
3. Else:
• Return “NO” as no such string is present which is lexicographically larger than ‘S’ of length ‘N’.

helper(ARR, CURRENT, P):

1. Base case: If ‘CURRENT’ is equal to 0:
• We can say that no such string is present which is lexicographically larger than ‘S’ of length ‘N’.
• So, we will return false.
2. Iterate a loop ‘i’ from ‘ARR[CURRENT] + 1’ to ‘P’ to find the proper character which can help us to get the next special string.
• If ‘CURRENT - 1’ is greater than 0 and ‘ARR[CURRENT - 1]’ equals ‘i’ then continue the loop by iterating the next character.
• If ‘CURRENT - 2’ is greater than 0 and ‘ARR[CURRENT - 2]’ equals ‘i’ then continue the loop by iterating the next character.
• If both the above conditions are not satisfied then we can say that we got a character for ‘CURRENT’ position.
• After assigning the value of ‘i’ to ‘ARR[CURRENT]’ we will return true.
3. If we are unable to find any character by iterating the loop then we have to change the character present left of it.
4. If ‘helper(ARR, CURRENT - 1, P)’ equals false then:
• We will return false as no such string is present which is lexicographically larger than ‘S’ of length ‘N’.
5. Else we will assign ‘ARR[CURRENT]’ as 1 and will find a character that can satisfy the properties of a special string by iterating a loop.
6. Iterate a loop ‘i’ from ‘ARR[CURRENT]’ to ‘P’ to find the proper character which can help us to get the next special string.
• If ‘CURRENT - 1’ is greater than 0 and ‘ARR[CURRENT - 1]’ equals ‘i’ then continue the loop by iterating the next character.
• If ‘CURRENT - 2’ is greater than 0 and ‘ARR[CURRENT - 2]’ equals ‘i’ then continue the loop by iterating the next character.
• If both the above conditions are not satisfied then we can say that we got a character for ‘CURRENT’ position.
• After assigning the value of ‘i’ to ‘ARR[CURRENT]’ we will return true.
7. If still, we are unable to get a character for ‘CURRENT’ position then we will return false.