first of all let me clear the constraints 1 <= T <= 10 , 1 <= N <= 1e5 and 1 <= K <= 26 ; where 'T' is the number of test cases and 'N' is the size of the string .
Q => A string is called beautiful if each character of the string is one of the first K letters of the English lowercase alphabet and that string does not contain any substring of length 2 or more which is a palindrome.
You are given the following: * Two non-negative integers N and K * A beautiful string S of length N
Task:- Determine the lexicographically smallest string of length N which is the beautiful and is lexicographically larger than string S. If no such string exists output will be -1. If multiple answer exist print any of them .
Input : Number of testcase => T Length of string => N The number of alphabets from starting which can be taken => K string => S
example : 2 4 5 eace 3 8 hgf
answers:
eadb -1
Note : I do not remember the time constraint ;
There was a really good blog post recently (that I can't find right now) that gave some problem solving strategies. I recall some of them being
These strategies I selected are common lines of thought in problems like "We call an array/graph/string/multiset/etc. 'interesting' if [some complicated condition] holds. Find some/all/smallest/any/number_of 'interesting' structures". This problem has that structure, and I recommend going through these strategies.
Well, I feel that's a great suggestion or step of sequence to approach such problems thanks for the help bro
We only need to check for palindromes of length 2 or 3 because palindromes of length $$$L$$$ imply palindromes of length $$$L-2$$$. This means same characters must be at least 3 apart.
From right-to-left we try to increase the $$$i^{th}$$$ character. Find the first position at which the smallest $$$S_i<x\leq K$$$ (treat chars as ints) does not equal to $$$S_{i-2}$$$ or $$$S_{i-1}$$$ exists and replace $$$S_i=x$$$. If such a position does not exist, the answer is -1. Now the suffix $$$S_{i+1..N}$$$ should be smallest possible. For $$$j>i$$$ choose the smallest character not equal to $$$S_{j-2}$$$ or $$$S_{j-1}$$$. Notice that the smallest beautiful string looks like $$$abcabcabc$$$.
This is $$$O(TN)$$$ because when $$$K-S_i\geq 3$$$ it will always be selected since we are only comparing against $$$S_{i-2}$$$ and $$$S_{i-1}$$$.
Yup , i got the approach , although it strike me after my OA ;) , but i guess that's perfectly fine for now. Thanks man.
Just for the reference this problem is also available on leetcode.
Problem no. : 2663
Thanks bro for the help I got the Q link: https://leetcode.com/problems/lexicographically-smallest-beautiful-string/description/
This is some text. Here is the java solution ~~~~~ // this is code int n=s.length(); char arr[]=s.toCharArray(); arr[n-1]++; for(int i=n-1;i<n;){ if(arr[i]=='a'+k){ arr[i--]='a'; if(i<0)return ""; arr[i]++; } else if((i>0&&arr[i]==arr[i-1])||(i>1&&arr[i]==arr[i-2]))arr[i]++; else i++; } return String.valueOf(arr);
~~~~~
The rest of the text.
This same problem is also available at Leetcode --> Lexicographically Smallest Beautiful String
Thanks bro for the help I got the Q link: https://leetcode.com/problems/lexicographically-smallest-beautiful-string/description/