next-higher-palindromic-number-same-digit.md

Next higher palindromic number using the same set of digits

Given a palindromic number N in the form of string. The task is to find the smallest palindromic number greater than N using the same set of digits as in N.

Sample Input

1
454121454

Sample Output

514424415

Solution

class Solution {
  public:

    string nextPalin(string N) {
        int len = N.size();

        if(len <= 3) {
            return "-1";
        }

        int mid = len/2;

        int first_small = -1;

        for(int i = mid - 1; i > 0; --i) {
            if(N[i-1] < N[i]){
                first_small = i-1;
                break;
            }
        }
        
        if(first_small < 0) {
            return "-1";
        }

        int later_small = first_small + 1;
        for(int i = later_small; i < mid; ++i) {
            if(N[later_small] > N[i] && N[i] > N[first_small]) {
                later_small = i;
            }
        }

        swap(N[later_small], N[first_small]);
        swap(N[len - later_small - 1], N[len - first_small - 1]);

        sort(N.begin() + first_small + 1, N.begin() + mid);
        sort(N.rbegin() + first_small + 1, N.rbegin() + mid);

        return N;
    }
};

Accepted