/*
Time Complexity : O(K)
Space Complexity : O(K)
where 'K' is the number of digits in the integer 'N'.
*/
long long findSuccessor(long long n)
{
string s = to_string(n);
int indexOfFirstSmallerDigit = -1;
int indexTobeSwapped = -1;
for (int i = s.size() - 2; i >= 0; i--)
{
if (s[i] < s[i + 1])
{
indexOfFirstSmallerDigit = i;
break;
}
}
// It means S is in non ascending order so return -1.
if (indexOfFirstSmallerDigit == -1)
{
return -1;
}
//Find the index where the digit is just greater than the digit at indexOfFirstSmallerDigit.
for (int i = s.size() - 1; i > indexOfFirstSmallerDigit; i--)
{
if (s[i] > s[indexOfFirstSmallerDigit])
{
indexTobeSwapped = i;
break;
}
}
swap(s[indexOfFirstSmallerDigit], s[indexTobeSwapped]);
// Reverse the digits at right side of indexOfFirstSmallerDigit.
int i = indexOfFirstSmallerDigit + 1, j = s.size() - 1;
while (i < j)
{
swap(s[i], s[j]);
i++;
j--;
}
long long ans = stoll(s);
return ans;
}