1842. Next Palindrome Using Same Digits

HardTwo PointersString
Leetcode Link

Problem Description

The challenge here is to find the next smallest palindrome that is larger than the given numeric string num. Remember that a palindrome is a sequence that reads the same backward as forward. The key here is 'numeric string', which implies that the input is not an integer but a string that represents a large numeric palindrome. The constraint of being a palindrome greatly reduces the complexity, as you only need to concentrate on half the string. Any permutation of the first half can be reflected to create the full palindrome. We're asked to rearrange the digits of the given palindrome to form the next larger palindrome. If no such rearrangement is possible, we must return an empty string.

Intuition

The solution follows from the observation that for a number to be the next larger palindrome, we need only to consider the first half of the digits. Once the first half is set, the second half is fixed as well, due to the mirror nature of a palindrome (the second half is a mirror of the first half). So, the approach involves finding the next greater permutation of the first half of the string's digits.

  1. Find the next permutation of the first half of the string. To do this, start from the end and move leftward, looking for the first digit that is smaller than the digit immediately to its right. Swap this digit with the smallest digit to its right that is larger than it and reverse the sequence after the original position of that smaller digit to get the lowest possible sequence there.

  2. After the first half is arranged in its next permutation, copy these digits in reverse order to the second half of the string to maintain the palindrome property.

  3. If no next permutation is possible for the first half, because it is already in its highest possible permutation (which implies that the entire number is the highest possible palindrome), return an empty string.

The provided Python function next_permutation() encapsulates the logic for generating the next permutation, and the remainder of the nextPalindrome function applies this result to the entire number to maintain the palindrome condition.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution involves manipulating the string of digits to find the desired palindrome. Here's a step-by-step explanation of how the code works:

Step 1: Convert the String to a List

First, the string num is converted to a list, nums, to allow for easy manipulation of individual characters. This step is crucial because strings in Python are immutable, so we cannot alter them in place. Lists, on the other hand, are mutable.

Step 2: Define the next_permutation Function

The next_permutation function finds the next lexicographically greater permutation of the provided list of characters, but only up to the middle of the list. This function is the key to the whole approach.

  • We use two pointers, i and j, to find the correct digits to swap.
  • Start with i at the second-to-last index and decrement it until we find a character that is smaller than the character to its immediate right.
  • Find the smallest digit greater than nums[i] from the right side of i and swap them.
  • Reverse the portion of the list after i + 1 to ensure we have the smallest possible value there, which will give us the next permutation.

Step 3: Call the next_permutation Function

We try to find the next permutation of the first half of the nums list. If no next permutation can be found, which would mean we are at the highest permutation, we return an empty string because there is no larger palindrome available with the same digits.

Step 4: Reflect the First Half to the Second Half

Assuming a next permutation is found, we traverse the first half and copy each character to its symmetrical position in the second half. This step ensures that we maintain the palindrome property of the string.

Step 5: Convert Back to String

Finally, we convert the list nums back to a string using "".join(nums) and return it as the next smallest palindrome that is larger than the original input.

This algorithm effectively leverages the properties of a palindrome to find the solution with as few changes as required. By transforming the input into a more manageable data structure (a list) and then applying a well-known algorithm (next permutation), we can efficiently deliver the required output.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's consider an example with the numeric string num = "12521". We have to find the next smallest palindrome greater than this number.

  1. Convert the String to a List: We convert the string to a list so we can manipulate it. num becomes nums = ['1', '2', '5', '2', '1'].

  2. Define the next_permutation Function: The next_permutation logic will look at the first half ['1', '2', '5'] (since we do not need to modify the whole list).

  3. Call the next_permutation Function: We look for the next permutation of the first half by applying the steps described in the content. First, we look for the first digit that is smaller than the digit immediately to its right when looking from right to left, which is 2. Then, we swap 2 with the digit just larger than it to the right, which is 5.

    • Before swap: ['1', '2', '5']
    • After swap: ['1', '5', '2']
    • Now, we reverse the sequence after the index 1 ('5'), but since there's only one element, it remains the same.

  4. Reflect the First Half to the Second Half: We now reflect this new order to the second half of the list. So, the first half of nums is ['1', '5', '2'], and the second half of nums is ['2', '5', '1'].

  5. Convert Back to String: We join the list back into a string, getting "15251". This is the next smallest palindrome larger than 12521.

Following these steps, the final output for the numeric string "12521" is "15251".

Solution Implementation

1from typing import List  # Importing List type for type annotations
2
3class Solution:
4    def nextPalindrome(self, num: str) -> str:
5        # Function to find the next palindrome larger than num
6        def next_palindrome_permutation(half: List[str]) -> bool:
7            # Reverse engineer the next permutation for a given half of the palindrome
8            n = len(half)
9            i = n - 2
10            # Find the first digit that can be increased
11            while i >= 0 and half[i] >= half[i + 1]:
12                i -= 1
13            if i < 0:
14                # If no such digit is found, no larger palindrome is possible
15                return False
16            j = n - 1
17            # Find the digit to swap with
18            while half[j] <= half[i]:
19                j -= 1
20            # Swap the two digits
21            half[i], half[j] = half[j], half[i]
22            # Reverse the sequence after the position of the swap
23            half[i + 1:] = half[i + 1:][::-1]
24            return True
25
26        # Split the number into two halves
27        half = list(num[:len(num)//2])
28        # Find the next permutation for the first half of the num
29        if not next_palindrome_permutation(half):
30            # If not possible, return an empty string
31            return ""
32
33        # Reconstruct the full palindrome from the permuted half
34        if len(num) % 2 == 0:
35            # Even length palindrome
36            next_num = "".join(half) + "".join(half[::-1])
37        else:
38            # Odd length palindrome: keep the middle character the same
39            next_num = "".join(half) + num[len(num)//2] + "".join(half[::-1])
40
41        return next_num
42
43# Example usage:
44# solution = Solution()
45# print(solution.nextPalindrome("12321"))  # Output would be the next palindrome larger than "12321"
46
1class Solution {
2
3    // Function to find the smallest palindrome larger than the given number
4    public String nextPalindrome(String num) {
5        // Convert the string to an array of characters for manipulation
6        char[] numArray = num.toCharArray();
7      
8        // Generate the next palindrome-like permutation if possible
9        if (!generateNextPermutation(numArray)) {
10            // If no greater permutation exists that is palindrome-like, return empty string
11            return "";
12        }
13      
14        // Get the length of the array
15        int length = numArray.length;
16      
17        // Complete the palindrome by mirroring the first half to the second half
18        for (int i = 0; i < length / 2; ++i) {
19            numArray[length - 1 - i] = numArray[i];
20        }
21      
22        // Convert the character array back to a string and return
23        return String.valueOf(numArray);
24    }
25
26    // Helper function to generate the next lexicographically greater permutation of a number
27    private boolean generateNextPermutation(char[] numArray) {
28        // Consider the midpoint of the array for permutation
29        int midpoint = numArray.length / 2;
30        // Start from the second to last character and move backwards to find the first character 
31        // which is less than its next one (to find the non-increasing suffix)
32        int i = midpoint - 2;
33        while (i >= 0 && numArray[i] >= numArray[i + 1]) {
34            --i;
35        }
36      
37        // If no such character exists, our number is the highest permutation
38        if (i < 0) {
39            return false;
40        }
41
42        // Find the smallest character on the right side of i which is greater than numArray[i]
43        int j = midpoint - 1;
44        while (numArray[i] >= numArray[j]) {
45            --j;
46        }
47      
48        // Swap the found characters
49        swap(numArray, i++, j);
50      
51        // Reverse the non-increasing suffix to make it the smallest sequence
52        for (j = midpoint - 1; i < j; ++i, --j) {
53            swap(numArray, i, j);
54        }
55      
56        // We found a valid next permutation
57        return true;
58    }
59
60    // Helper function to swap two characters in an array
61    private void swap(char[] numArray, int i, int j) {
62        char temp = numArray[i];
63        numArray[i] = numArray[j];
64        numArray[j] = temp;
65    }
66}
67
1#include <algorithm> // Include for std::next_permutation
2#include <string>    // Include for std::string
3
4class Solution {
5public:
6    // Function to find the next palindrome greater than the given number
7    string nextPalindrome(string num) {
8        int length = num.size(); // Store the length of the input number
9        // Extract the first half of the number (since palindrome is symmetric)
10        string firstHalf = num.substr(0, length / 2);
11
12        // Generate the next lexicographically greater permutation of the first half
13        // If no such permutation exists (meaning it is the highest possible permutation),
14        // then there is no greater palindrome, and we return an empty string
15        if (!next_permutation(begin(firstHalf), end(firstHalf))) {
16            return ""; // Return an empty string as there is no next greater palindrome
17        }
18
19        // Build the next greater palindrome using the permuted first half
20        for (int i = 0; i < length / 2; ++i) {
21            num[i] = firstHalf[i]; // Copy the first half to the front of 'num'
22            num[length - i - 1] = firstHalf[i]; // Mirror the first half to the back of 'num'
23        }
24
25        // If the length is odd, the middle character remains unchanged
26        // in the new palindrome.
27
28        return num; // Return the next greater palindrome
29    }
30};
31
1function nextPalindrome(num: string): string {
2    // Convert the input string to an array of characters
3    const numArray = num.split('');
4    // Get the half-length of the array for reference
5    const halfLength = numArray.length >> 1;
6
7    // Attempt to find the next permutation for the first half of the array
8    if (!nextPermutation(numArray)) {
9        return ''; // If no next permutation exists, return an empty string
10    }
11
12    // Reflect the first half of the array to the second half to form a palindrome
13    for (let i = 0; i < halfLength; ++i) {
14        numArray[numArray.length - 1 - i] = numArray[i];
15    }
16
17    // Join the array back into a string and return the result
18    return numArray.join('');
19}
20
21function nextPermutation(nums: string[]): boolean {
22    // Determine the central index based on half the length of the nums array
23    const halfLength = nums.length >> 1;
24    // Find the rightmost character in the first half that is smaller than the character next to it
25    let i = halfLength - 2;
26    while (i >= 0 && nums[i] >= nums[i + 1]) {
27        i--;
28    }
29
30    // If no such character exists, then this is the last permutation
31    if (i < 0) {
32        return false;
33    }
34
35    // Find the rightmost character in the first half that is greater than the found character
36    let j = halfLength - 1;
37    while (j >= 0 && nums[i] >= nums[j]) {
38        j--;
39    }
40
41    // Swap the found characters
42    [nums[i], nums[j]] = [nums[j], nums[i]];
43
44    // Reverse the part of the array after the found character to get the next permutation
45    for (i = i + 1, j = halfLength - 1; i < j; ++i, --j) {
46        [nums[i], nums[j]] = [nums[j], nums[i]];
47    }
48
49    // Return true as the next permutation is successfully found
50    return true;
51}
52
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the minimum element can be found in:

Time and Space Complexity

Time Complexity

The function next_permutation involves a reversing operation which in worst-case can take O(n/2) time, where n is the length of the nums (half the length of the string because the function only considers half of the string for permutation). Furthermore, finding the positions i and j can each take up to O(n/2) in the worst case. Thus, each call to next_permutation is O(n).

The overall time complexity of the nextPalindrome function is primarily determined by the call to next_permutation and the subsequent loop that mirrors the first half of the nums list to the second half. This loop also takes O(n/2) time since it operates up to the midpoint of the list.

Adding these complexities together, the total time complexity of the nextPalindrome function remains O(n) since constant factors are ignored in Big O notation and multiple O(n) operations still result in O(n).

Space Complexity

The nextPalindrome function creates a list nums of characters based on the input string, which takes O(n) space, where n is the length of the input string.

The in-place reversal within the next_permutation function does not consume extra space beyond minor variables, and the swapping of i and j also does not require additional space beyond the existing array.

Therefore, the overall space complexity of the nextPalindrome function is O(n), accounting for the space needed for the nums list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫