Next Greater Palindrome

Here is the full interview question "Next Greater Palindrome - Uber Coding Interview | ShowOffer" from Uber on ShowOffer.io:

Problem Statement: Given a string s, find the smallest string greater than s that contains the same digits as s and is a palindrome. If no such string exists, return an empty string.

Examples:

1. Input: "ababa" Output: "abcba"

2. Input: "abaaa" Output: "acaac"

3. Input: "abc" Output: ""

Constraints:

• 1 <= s.length <= 10^5

Hints:

1. Try to find the next palindrome by modifying the middle character(s) of the string.
2. If the string is already a palindrome, try to increment the first half of the string.

Solution: To solve this problem, you can follow these steps:

1. Reverse the input string and compare it with the original string. If they are the same, it means the string is already a palindrome. In this case, try to increment the first half of the string.
2. If the string is not a palindrome, find the first character from the left that is smaller than the corresponding character from the right. Then, find the smallest character to the right of the found character that is greater than it.
3. Swap the found character with the smallest character to its right that is greater than it. This will make the string a palindrome.
4. Reverse the substring between the found character and the character to its right, and append it to the left of the found character. This will give you the smallest palindrome greater than the input string.

Here's a Python implementation of the solution:

`python def nextGreaterPalindrome(s: str) -> str: n = len(s) rev = s[::-1] if s == rev: half = s[:(n + 1) // 2] next_half = str(int(half) + 1) if len(next_half) > len(half) or (len(next_half) == len(half) and next_half < half): return "" return next_half[::-1] + (next_half if n % 2 == 0 else next_half[:-1])

for i in range(n - 1, -1, -1):
    if s[i] < s[i - 1]:
        break

if i == 0:
    return ""

for j in range(n - 1, i - 1, -1):
    if s[j] > s[i - 1]:
        break

half = list(s[:i])
half[j], half[i - 1] = half[i - 1], half[j]
half[i:] = half[:i][::-1]
return "".join(half)

`

This solution has a time complexity of O(n) and a space complexity of O(n), where n is the length of the input string.