Hit enter after type your search item
Wzy Word

HERE ARE THE WORLD'S NEWS

Leetcode problem Break a Palindrome

/
/
/
691 Views
img

Break a palindrome is a recent question from LeetCode, We are given a palindromic string we should replace one character with some other English lowercase character and the resulting string cannot be a palindromeAmong possible outputs of that, We should find the one which is lexicographically smallest possible so in a dictionary of sorted words, sorted first by first letter than second and so on, it should be as high as possible, It should be smallest one

Here, Given abccba, This is a palindrome We can change the second character from b to a, now this string is not a pallindrome But in the second example, You cannot change letter a to anywhere else so it wouldn't be a pallindrome, always a string of length 1 is a palindrome and then you output an empty string, it means there is no solution The length of the given string is up to 1000 Lexicographic minimum means that we should first minimize the first character, if it is already letter 'a' maybe it's better to then minimize the second character and so on, and here indeed we just go from left to right and the first non-'a', we can change into 'a' This way because we have a change, Previously it was a palindrome So we had an equality here, 'b' is equal 'b', by changing 'b' to something else, We make the string to be non palindrome So all the conditions are satisfied and we got the minimum possible string, but does it always work? Let's see some other examples 'bbb,' is it okay here to go from left to right and to change the first possible character to 'a' 'b' we change to 'a' and that's it Because we have now 'abb', not a palindrome and this is indeed the lexicographically smallest possible string we can get What if the string just contains of letters 'a'? 'aaaa', then we cannot change anything into 'a' because it will be still the same string, instead we need to change something to another letter, to 'b', 'c' or 'z', for sure 'b' will be best because it's smallest lexicographically and which letter should we choose, we have options like 'baaa' or 'abaaa' and so on or eventually 'aaab' and this one is smallest lexicographically because the prefix is for a long time just 'a', it will be first in dictionary of those Words of this length with letters 'a' and 1 letter 'b' So 'aaaa' should be changed into this string our solution so far is go from characters from left to right, the first character different than 'a', change it to 'a' and print the resulting string, if you have only 'a's Then change the last character to 'b', but there is a catch here, you can think for a moment what it is

Often in problems about pallindromes, even and odd lengths are completely different and for odd length there is one very special character, the middle one if we try to change this character to something else, Let's say from 'c' to 'a' Then the string will remain to be a palindrome, because we had this equality, this equality between those two strings for example, let's say 'aaaa' and this 'c', changing it into 'a' will give you still a palindrome This operation is forbidden and instead It's best to change this last character 'a' into 'b', Just like for a string of just characters 'a', I'm going to quickly implement the brute force solution to show you O(N*N) version and then I will move to the intended solution that I've just described For my convenience I will change the name pallindrome into s and I will create n, the length of palindrome s and now the brute force would be to try to change every character Into maybe every possible letter from 'a' to 'z' If the current ith letter is different than character then Try to change it It will be the same string, But s2[i] is changed into this new character And now if this is not a palindrome, if (!ispallindrome) of s2, then consider it to be the answer

Here I need two functions, I need is_palindrome Maybe let's call it s2 because this is what I had here, obviously you can implement that and if !pallindrome then consider it, let's say that answer will be string initially empty, at the end I will return it and here if answer is still empty then we found a better string Then answer is s2 Yes, this is a new string But in other case answer is minimum of answer and s2, in C++ by default two strings will be compared lexicographically and this will be full solution working in and O(N*N*alphabet) complexity This is a for loop of size n, this is for loop of size 26, size of the alphabet and checking for example palindrome or creating a new string or here modifying answer to be a new string each of that is O(n) If you multiply that because those are nested things, one inside the other you will get O(N*N*alphabet), let's say the alphabet size is k, we know it is 26, So actually we can skip this value But it's quadratic solution still good enough for constraints of 1000 But we came up with a better solution, with a linear one So let's implement that one still maybe leaving N – the length of the string I know that index 0 should be matched with n-1 1 with n-2, and so on, In general i is matched with n-1-i So this is one possible way to make an if to check if I'm exactly in the middle, it is if i==j then this is something special, I will say continue, I cannot change this character, It is forbidden, I'm exactly in the middle Otherwise if s[i]!='a' Then change it and return Here I want to say the last character changed into 'b' and return s

But well here, when do we return an empty string, there was an example for that even in the statement We should use examples in the statement to our advantage and that was a case of string of language just one because then the only character is the middle character, so I will say If n is 1 then return empty, and then for sure here, I'm changing not the middle character, I will submit this and This time the complexity, it is just linear, This is O(N) because we have a for loop, single for loop of size N and returning string s it has linear complexity of O(N) but we do it just once, so it's not that this for loop will multiple times return s, and all those other operations, they are constant One possible modification here is to just do this But you need to be careful about rounding, if you want to say N/2, rounded down or up If you want to say that you check characters from the beginning to the middle excluding the middle And then you don't need this check at all and let's see if this would work For the length of 4, 0 1 2 3 so an even length of the string n/2 would be 2 so this would say while i is smaller than 2 for n equal to 4 and it will check those two character, It will try to change them from something else to 'a' and it is correct If both those are 'a' and also both of those are 'a' because it's a pallindrome For n equal to 5 Let's also check that here We have a 2, so I will have i < 2, this is the condition and it will again just check indices 0 and 1 it works, I don't want to consider changing element 2 into something else because it's the middle character and changing it will still give me a palindrome Let me know in the comments if you enjoyed this easier shorter video, See you next time, Bye 🙂

Source: Youtube

This div height required for enabling the sticky sidebar