Given a string of lowercase alphabets A of size N. You are allowed to reverse any substring of the array (can't reverse more than one substring) Return the lexicographically smaller string you can make. Refer the attached Image for original question. Thanks!! PS. This Question is from my college coding competition which has ended. So now seeking help.
Backtracking?
Let's say the string is S. Compute the lexicographically smallest suffixes of S.reverse() + S using suffix array. Then take the lexicographically smallest suffix with length at least S + 1. Let its length be "len". Then S.substring(0, len-S) is the substring you should reverse. Should be O(N) time O(N) space.
I don't see why it should work. Can you prove it?
Suppose the string is "raman". Then S.reverse() + S is: "namarraman" Suffix array, represented by the index in the string that the suffix starts with, is: [6, 1, 8, 3, ...] Suffix starting at index 6 has len less than S + 1, so we skip that. Suffix starting at index 1 has len more than S + 1, so we use that. It's len is 9, so the substring we want to reverse is S.substring(0, 9-5) = S.substring(0, 4) = "rama". Reversing this substring gives us "amarn", the correct answer.
Well from the top of my head and without doing any deep analysis, you can achieve this by looking at every substring of the original string in o(n^2) and reversing the current substring you are looking at in place which will take another o(n) then compare the newly generated string to the minimum string you have so far, this will take a total of o(n^3 + 2n) it is the naive solution tho and not the most optimal
A better approach could be dynamic programming where you draw the full tree, I bet there are subproblems to discover so you can cache them, which will turn the solution into o(n^2)
Scan from left until you find a non-increasing letter, mark position A. Keep going to the right and find rightmost index B of the smallest letter in the remaining string. Reverse between A and B. O(N) time.
abcdefba First non increasing letter is f -> b. Right most index of smallest letter in remaining string is the last a. Reversing those doesn't give the correct answer, which is aabfedcb.
What's the time limit? For 1s limit and N < 200, brute force should be fast enough
Interviewer: Can you do better?
ofc interviews are different, but for contests it's important to know what is good enough to pass in order to allocate your time more effectively
Scan the whole string, to get the frequency of each char, then you should know the smallest string, consider this the "correct" string. Scan the 2nd round, to find the first position A containing the "wrong" char, and position B where the "correct" char for A is, reverse substr (A, B)
Can be done using greedy approach. How can we achieve the lexographically smallest substring? Lets say if we had xbcdas .. lexographically smallest would be the one that starts with smallest character in the string.. in this case 'a' .. so answer should be adcbxs .. So first we try to get the smallest character at first position.. if their are multiple of them .. we look at their second last characters and see which one is smaller . If the smallest character is already at the first position .. we try to get the smallest character ( or the second smallest) at the second position and so on .
Just scan from right to left for the lowest increasing substring, start from the last char 'x' as soon you find a lower char 'y' you have a new best solution, if you find the same char 'x' keep scanning for the next chars, O(n) time since you will never compute the same char twice
Oh hey, I use this at my job everyday in the real world! So glad companies are asking which substring to reverse to find the overall string that is lexicographically the smallest!
😂 Actually this was asked in Interviewbit coding competition. Don't know if it will be asked in Interviews , Any idea?
I mean...you’re the one who chose to work for a company owned by Alphabet.