Given an integer array queries and a positive integer intLength, return an array answer where answer[i] is either the queries[i]th smallest positive palindrome of length intLength or -1 if no such palindrome exists.
A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.
Example 1:
Input: queries = [1,2,3,4,5,90], intLength = 3 Output: [101,111,121,131,141,999] Explanation: The first few palindromes of length 3 are: 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ... The 90th palindrome of length 3 is 999.
Example 2:
Input: queries = [2,4,6], intLength = 4 Output: [1111,1331,1551] Explanation: The first six palindromes of length 4 are: 1001, 1111, 1221, 1331, 1441, and 1551.
Constraints:
1 <= queries.length <= 5 * 1041 <= queries[i] <= 1091 <= intLength <= 15One way to solve the problem is by utilizing the properties of palindromes. For any given length of palindrome — whether it is odd or even, it can be generated by mirroring the relevant portion of the number. Using a step-counter, iterate through possible leading halves and mirror these to generate palindromes. This approach takes advantage of simple arithmetic to generate palindromes.
This Python function defines a helper function kthPalindrome to compute the k-th smallest palindrome with given length. It calculates the necessary half length, checks if k is beyond the possible range, constructs the half palindrome, and then mirrors it appropriately.
JavaScript
Java
Time Complexity: O(n), where n is the length of queries. For each query, the operation is constant time.
Space Complexity: O(1), since computations do not require extra space related to the size of the input.
In this approach, instead of calculating using a mirrored half, iterate over possible values and construct palindromes digit by digit. For each digit length possibility, cross verify each candidate to identify queries[i] number of palindromes. This is more direct but potentially less efficient due to the complete construction attempts.
This C code anatomizes the process of constructing numeric arrays and copying to create palindrome integers.
The iterative construction may be less optimal when compared to direct computations.
Time Complexity: O(n) for queries.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Two-parts Mirror Approach | Time Complexity: O(n), where n is the length of queries. For each query, the operation is constant time. |
| Iterative Digit Construction | Time Complexity: O(n) for queries. |
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 629,143 views views
Watch 9 more video solutions →Practice Find Palindrome With Fixed Length with our built-in code editor and test cases.
Practice on FleetCode