Given a string S of numbers of size N, the duty is to search out the minimal variety of operations required to vary a string into palindrome and we are able to carry out the next process on the string :
- Select an index i (0 ≤ i < N) and for all 0 ≤ j ≤ i, set Sj = Sj + 1 (i.e. add 1 to each component within the prefix of size i).
Be aware: Whether it is unimaginable to transform S to a palindrome, print −1.
Examples:
Enter: S = “1234”
Output: 3
Rationalization: We will carry out the next operations:
Choose i=1, “1234”→”2234″
Choose i=2, “2234”→”3334″
Choose i=1, “3334”→”4334″
Therefore 3 variety of operations required to vary a string into palindrome.Enter: S = “2442”
Output: 0
Rationalization: The string is already a palindrome.
Method: The issue might be solved based mostly on the next remark:
Initially test if the string is already a palindrome or not. If it isn’t a palindrome, then it may be transformed right into a palindrome provided that all the weather in the precise half of the string is bigger than those within the left half and the distinction between the characters nearer to finish is bigger or equal to the distinction between those nearer to the centre.
Observe the steps talked about beneath to implement the thought:
- First set i = 0, j = N -1 and max = IntegerMaximumValue and ans = 0.
- After that iterate a loop till j > i
- Test if S[j] < S[i], whether it is true then we are able to’t change the string into palindrome and return -1.
- In any other case, take absolutely the distinction of S[j] and S[i] and examine it with ans to search out the utmost between them:
- If the utmost worth is lower than absolutely the distinction of S[j] and S[i], return -1.
- In any other case, max is absolutely the distinction between S[j] and S[i]
- Return ans which is the minimal variety of operations required to vary a string right into a palindrome.
Under is the implementation of the above strategy.
Java
|
|
Time Complexity: O(N)
Auxiliary House: O(1)
