SauravSingh3296's blog

Need help for solving a Question asked in google .

By SauravSingh3296, history, 4 weeks ago, In English

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 ;

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  1. Find alternate characterizations of complicated conditions
  2. Solve the smallest interesting case by hand
  3. Look for necessary conditions. Are they already sufficient? If not, what is the "weakest strengthening" which makes them sufficient?
  4. Repeat (3), swapping "necessary" and "sufficient".

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.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, I feel that's a great suggestion or step of sequence to approach such problems thanks for the help bro

    → Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

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}$$$.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup , i got the approach , although it strike me after my OA ;) , but i guess that's perfectly fine for now. Thanks man.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just for the reference this problem is also available on leetcode.

Problem no. : 2663

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply