Next Palindrome Using Same Digits - Practice Coding Problems

Next Palindrome Using Same Digits - Problem

You are given a numeric string num, representing a very large palindrome.

Return the smallest palindrome larger than num that can be created by rearranging its digits. If no such palindrome exists, return an empty string "".

A palindrome is a number that reads the same backward as forward.

Input & Output

Example 1 — Basic Increment

$ Input: num = "12321"

› Output: "13031"

💡 Note: Next permutation of left half "123" is "130". Mirroring gives "13031" which is the smallest palindrome larger than "12321".

Example 2 — All 9s

$ Input: num = "99"

› Output: ""

💡 Note: No larger palindrome can be formed using the same digits since both digits are already maximum (9).

Example 3 — Single Digit

$ Input: num = "1"

› Output: ""

💡 Note: Only one digit available and it's not the maximum, but no larger single-digit palindrome exists using same digit.

Constraints

1 ≤ num.length ≤ 10⁵
num consists of only digits
num represents a valid palindrome

Visualization

Tap to expand

Understanding the Visualization

Input Palindrome

Given palindrome string that reads same forwards/backwards

Find Next Pattern

Use next permutation on left half to find next larger arrangement

Mirror Result

Create complete palindrome by mirroring left half to right

Key Takeaway

🎯 Key Insight: Only need to find next permutation of left half, then mirror to create complete palindrome

Asked in

G Google 35 a Amazon 28 f Facebook 22 M Microsoft 18

The key insight is that we only need to find the next permutation of the left half of the palindrome, then mirror it to create the complete result. The optimal approach uses the next permutation algorithm on just the left half. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Next Permutation on Half	O(n)	O(n)	Apply next permutation algorithm only to the left half, then mirror to create palindrome
Generate All Palindromes	O(n! × n)	O(n! × n)	Generate all possible palindromes from the digits and find the next larger one
Two Pointers with Next Permutation	O(n²)	O(n)	Use two pointers to find the next lexicographically larger palindrome

Next Permutation on Half — Algorithm Steps

Extract left half of palindrome
Find next lexicographical permutation of left half
Mirror left half to right half to form complete palindrome
Return result or empty string if no next permutation exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Left Half

Take left half including middle digit for odd length

Next Permutation

Apply next permutation algorithm to left half only

Mirror Result

Create full palindrome by mirroring left half to right

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void reverse(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}

int nextPermutation(char* s, int len) {
    // Find the largest index i such that s[i] < s[i + 1]
    int i = len - 2;
    while (i >= 0 && s[i] >= s[i + 1]) {
        i--;
    }
    
    // If no such index exists, return 0
    if (i < 0) {
        return 0;
    }
    
    // Find the largest index j such that s[i] < s[j]
    int j = len - 1;
    while (s[j] <= s[i]) {
        j--;
    }
    
    // Swap s[i] and s[j]
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
    
    // Reverse the suffix starting at s[i + 1]
    reverse(s, i + 1, len - 1);
    
    return 1;
}

char* solution(char* num) {
    static char result[1000];
    int n = strlen(num);
    
    // Get left half including middle for odd length
    char leftHalf[500];
    int halfLen = (n + 1) / 2;
    strncpy(leftHalf, num, halfLen);
    leftHalf[halfLen] = '\0';
    
    // Find next permutation of left half
    if (!nextPermutation(leftHalf, halfLen)) {
        strcpy(result, "");
        return result;
    }
    
    // Create palindrome by mirroring
    strcpy(result, leftHalf);
    
    // Add mirrored part (exclude middle for odd length)
    int resultLen = strlen(result);
    for (int i = n / 2 - 1; i >= 0; i--) {
        result[resultLen] = leftHalf[i];
        resultLen++;
    }
    result[resultLen] = '\0';
    
    return result;
}

int main() {
    char num[1000];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    printf("%s\n", solution(num));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find next permutation, O(n) to create result palindrome

✓ Linear Growth

Space Complexity

O(n)

Extra space to store the result palindrome string

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Next Permutation on Half — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler