hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Next smaller Palindrome


  • Approach:

    1. Run the loop from i = 0 to (N/2) or (N/2 - 1)

    2. For ith digit, continue checking if the current digit is 0.

    3. If not then reduce the value by 1.

    4. If its value becomes greater than or equal to zero then change the corresponding (n - i - 1)th digit.

    5. And also change the digits from (i +1) to (n-i+1) to 9.

    6. If none of them satisfy then we need to reduce the string length by 1.

    7. If the reduced length becomes 0, then return 0.

    8. Else fill the entire (N-1) elements with 9.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1)


Code [C++]

#include <bits/stdc++.h>

string nextSmallerPalindrome(string &s) {

int n = s.size(), idx = (n%2 == 1) ? n/2 : n/2 - 1;

while(idx >= 0){

if(s[idx] == '0') ;

else if((s[idx] != '1') || (s[idx] == '1' && idx != 0)){

s[idx] = ((s[idx] - '0') - 1) + '0';

s[n-idx-1] = s[idx];

for(int i=idx+1; i<n-(idx+1); i++){

s[i] = '9';

}

return s;

}

idx--;

}

if(n - 1 == 0) return "0";

s = "";

for(int i=0; i<n-1; i++) s += '9';

return s;

}