Special String

Moderate
0/80
Average time to solve is 25m
14 upvotes
Asked in companies
MicrosoftOptum

Problem statement

A string ‘S’ is said to be special if each of its characters is one of the first ‘P’ letters of the English alphabet and ‘S’ doesn't contain any palindrome contiguous substring of length 2 or more. You will be given a special string ‘S’ of length ‘N’, find the lexicographically next special string of the same length, or else state that such string does not exist. Print the output string if it exists, otherwise, print "NO" (without quotes).

A string “s1” is a substring of another string “s2” if “s2” contains the same characters as in “s1”, in the same order and in a continuous fashion also.

Example: Given a string “cba” and ‘P’ equals 3. So, the next strings which are lexicographically bigger than string ‘S’ are “cbb”, “cbc”, “cca”, “ccb” and “ccc” of size 3. But all of them have a palindrome substring of the size at least 2. So, we will return “NO” as output. If the given string is “cbd” and ‘P’ equals 4 then the next string will be “cda” and it is special. So, we can return an output here.

Note:

It is guaranteed that the input string is special.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 4
abcd
4 4
dcbd
Sample Output 1:
abda
NO
Explanation For Sample Input 1:
In the first test case, the next string which is lexicographically larger than “abcd” is “abda” and it is special. Thus, we will return it.

In the second test case, the strings which are lexicographically larger than “dcbd” of length 4 are “dcca”, “dccb”, “dccc”, “dccd”, “dcda”, “dcdb”, “dcdc”, “dcdd”,  “ddaa”, “ddab”, “ddac”, “ddad”, “ddba”, “ddbb”, “ddbc”, “ddbd”, “ddca”, “ddcb”, “ddcc”, “ddcd”, “ddda”, “dddb”, “dddc” and “dddd” which are all not special. Thus, we will return “NO”.
Sample Input 2:
2
4 3
abca
2 4
ad
Sample Output 2:
acba
ba
Explanation For Sample Input 2:
In the first test case, the next string which is lexicographically larger than “abca” and also special is “acba” and it is special. Thus, we will return it.

In the second test case, the next string which is lexicographically larger than “ad” is “ba” and it is special. Thus, we will return it.
Hint

Can you think from the input given, that it is a special string?

Approaches (1)
Greedy Approach

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.
Time Complexity

O(N*P), where N is the length of the string ‘S’ and P is the letter that can be used for forming the string.

 

Because in the worst case we had to check for all the positions and for all positions we had to check all letters. So, we have to iterate through the entire length and for all the characters. Thus, the time complexity is O(N*P).

Space Complexity

O(N) where N is the length of the string ‘S’.

 

Because we are using an extra array for storing the character value of the entire string ‘S’.

 

Code Solution
(100% EXP penalty)
Special String
Full screen
Console