Minimize operations to make String palindrome by incrementing prefix by 1 – GeeksforGeeks

Given a string S of numbers of length N, the task is to find the minimum number of operations required to change a string into palindrome and we can perform the following procedure on the string :

• Choose an index i (0 ≤ i < N) and for all 0 ≤ j ≤ i, set S_j = S_j + 1 (i.e. add 1 to every element in the prefix of length i).

Note: If it is impossible to convert S to a palindrome, print −1.

Examples:

Input: S = “1234”
Output: 3

Explanation: We can perform the following operations:
Select i=1, “1234”→”2234″
Select i=2, “2234”→”3334″
Select i=1, “3334”→”4334″ 
Hence 3 number of operations required to change a string into palindrome.

Input:  S = “2442”

Output: 0
Explanation: The string is already a palindrome.

Approach: The problem can be solved based on the following observation: 

Initially check if the string is already a palindrome or not. If it is not a palindrome, then it can be converted into a palindrome only if all the elements in the right half of the string is greater than the ones in the left half and the difference between the characters closer to end is greater or equal to the difference between the ones closer to the centre.

Follow the steps mentioned below to implement the idea:

• First set i = 0, j = N -1 and max = IntegerMaximumValue and ans = 0.
• After that iterate a loop until j > i 
  • Check if S[j] < S[i], if it is true then we can’t change the string into palindrome and return -1.
  • Otherwise, take the absolute difference of S[j] and S[i] and compare it with ans to find the maximum between them:
    • If the maximum value is less than the absolute difference of S[j] and S[i], return -1.
    • Otherwise, max is the absolute difference between S[j] and S[i]
• Return ans which is the minimum number of operations required to change a string into a palindrome.

Below is the implementation of the above approach.

Time Complexity: O(N) 
Auxiliary Space: O(1)