Given a string S of size N consisting of characters ‘0’ to ‘9’, the task is to print the longest palindrome that can be formed using a subset of the given string S that has the least numerical value among all the possible longest palindromes.
Examples:
Input : S = “44884947137”
Output : 447818744
Explanation : There are many palindromic integers
which can be formed from the given string like:
484, 7844487, 84448, 447818744
But 447818744 is the longest palindrome with minimum numeric value.Input : S = “4947137”
Output : 47174
Approach: Use the below idea to solve the problem:
Palindrome can have a maximum of 1 odd number of characters. So use the frequency of the characters to form the longest palindrome with the least integer value by placing the smallest integer characters at both ends.
Follow the below steps to solve the problem:
- Create a count array of size 10 to store the frequency of characters 0 to 9.
- Traverse the string and increment the frequency of each character.
- Create an empty string ans to store the answer.
- Traverse the frequency array to find the first non-zero character with the frequency of at least 2, and add it to the answer.
- If the answer is not empty:
- Run loop on frequency array from 0 till 9 and add the character to ans while the frequency of the character is greater than 1 and subtract 2 from the character frequency.
- Store the current ans in res variable.
- Run a loop from 0 to 9 and add the smallest element (if present) with the frequency of at least one to ans to consider odd-length palindromes.
- Add the reversed res to ans string to generate the palindrome.
- Return ans as the final answer.
Below is the implementation for the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the// longest palindromic arrangement with// minimum numeric valuestring palindrome_length(string s){ int count[10] = { 0 }; for (char c : s) { // Counting the frequency count++; } // String to store the longest // palindrome string ans = ""; for (int i = 1; i <= 9; i++) { // Adding first non zero character // to avoid leading zeroes if (count[i] > 1) { ans += '0' + i; count[i] -= 2; break; } } for (int i = 0; i <= 9; i++) { // If no character is present // atleast twice if (ans.size() == 0) { break; } // Making the longest palindrome // using the remaining digits while (count[i] > 1) { ans += '0' + i; count[i] -= 2; break; } } // Storing the string into a // temporary string string rev = ans; for (int i = 0; i <= 9; i++) { // For odd length palindromes one // odd character is allowed at // middle if (count[i] > 0) { ans += '0' + i; break; } } // Reversing the temporary string reverse(rev.begin(), rev.end()); ans = ans + rev; return ans;}// Driver Codeint main(){ string s = "44884947137"; // Function call string ans = palindrome_length(s); cout << ans; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to find the // longest palindromic arrangement with // minimum numeric value static String palindrome_length(String s) { int count[] = new int[10]; for (char c : s.toCharArray()) { // Counting the frequency count++; } // String to store the longest // palindrome String ans = ""; for (int i = 1; i <= 9; i++) { // Adding first non zero character // to avoid leading zeroes if (count[i] > 1) { ans += (char)('0' + i); count[i] -= 2; break; } } for (int i = 0; i <= 9; i++) { // If no character is present // atleast twice if (ans.length() == 0) { break; } // Making the longest palindrome // using the remaining digits while (count[i] > 1) { ans += (char)('0' + i); count[i] -= 2; break; } } // Storing the string into a // temporary string String rev = ans; for (int i = 0; i <= 9; i++) { // For odd length palindromes one // odd character is allowed at // middle if (count[i] > 0) { ans += (char)('0' + i); break; } } StringBuilder sb = new StringBuilder(rev); sb = sb.reverse(); ans = ans + sb.toString(); return ans; } public static void main (String[] args) { String s = "44884947137"; // Function call String ans = palindrome_length(s); System.out.println(ans); }}// This code is contributed by aadityaburujwale. |
Python3
# Function to find the# longest palindromic arrangement with# minimum numeric valuedef palindrome_length(s): count = [0] * 10 for c in s: # Counting the frequency count[int(c) - int('0')] += 1 # String to store the longest # palindrome ans = "" for i in range(1, 10): # Adding first non zero character # to avoid leading zeroes if count[i] > 1: ans += str(i) count[i] -= 2 break for i in range(0, 10): # If no character is present # at least twice if len(ans) == 0: break # Making the longest palindrome # using the remaining digits while count[i] > 1: ans += str(i) count[i] -= 2 break # Storing the string into a # temporary string rev = ans for i in range(0, 10): # For odd length palindromes one # odd character is allowed at # middle if count[i] > 0: ans += str(i) break # Reversing the temporary string rev = rev[::-1] ans = ans + rev return ans# Driver Codeif __name__ == "__main__": s = "44884947137" # Function call ans = palindrome_length(s) print(ans)# This code is contributed by akashish__ |
C#
using System;using System.Linq;public class GFG{ // Function to find the // longest palindromic arrangement with // minimum numeric value static string palindrome_length(string s) { int[] count = new int[10]; foreach(char c in s) { // Counting the frequency count++; } // String to store the longest // palindrome string ans = ""; for (int i = 1; i <= 9; i++) { // Adding first non zero character // to avoid leading zeroes if (count[i] > 1) { ans += (char)('0' + i); count[i] -= 2; break; } } for (int i = 0; i <= 9; i++) { // If no character is present // atleast twice if (ans.Length == 0) { break; } // Making the longest palindrome // using the remaining digits while (count[i] > 1) { ans += (char)('0' + i); count[i] -= 2; break; } } // Storing the string into a // temporary string string rev = ans; for (int i = 0; i <= 9; i++) { // For odd length palindromes one // odd character is allowed at // middle if (count[i] > 0) { ans += (char)('0' + i); break; } } // Reversing the temporary string rev = new string(rev.Reverse().ToArray()); ans = ans + rev; return ans; } // Driver Code static public void Main() { string s = "44884947137"; // Function call string ans = palindrome_length(s); Console.WriteLine(ans); }}// This code is contributed by akashish__ |
Javascript
// JavaScript code for the above approach// Function to find the// longest palindromic arrangement with// minimum numeric valuefunction palindrome_length(s) { let count = {}; for (let c of s) { // Counting the frequency if (!count) { count = 1; } else { count++; } } // String to store the longest // palindrome let ans = ""; for (let i = 1; i <= 9; i++) { // Adding first non zero character // to avoid leading zeroes if (count[i] > 1) { ans += i; count[i] -= 2; break; } } for (let i = 0; i <= 9; i++) { // If no character is present // at least twice if (ans.length == 0) { break; } // Making the longest palindrome // using the remaining digits while (count[i] > 1) { ans += i; count[i] -= 2; break; } } // Storing the string into a // temporary string let rev = ans; for (let i = 0; i <= 9; i++) { // For odd length palindromes one // odd character is allowed at // middle if (count[i] > 0) { ans += i; break; } } // Reversing the temporary string rev = rev.split("").reverse().join(""); ans = ans + rev; return ans;}// Driver Codelet s = "44884947137";// Function calllet ans = palindrome_length(s);console.log(ans);// This code is contributed by akashish__ |
Output
447818744
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
