Maximize value of Palindrome by rearranging characters of a Substring - Coding

Given a string S of length N (1 ? N ? 10³) that consists of a digit from ‘0’ to ‘9’, the task is to find the maximum value of palindrome that could be generated by rearranging characters of a substring.

Examples:

Input: S = “91242459”
Output: 42524
Explanation: Rearrange the substring ‘24245’ to form a palindrome. This will give the maximum value of the palindrome.

Input: S = “25242459”
Output: 5429245

An approach using BitMasking:

The idea is to find the largest substring that we can rearrange to form palindrome. As in a palindrome every character must be present even number of times except for a maximum of 1 element. So XOR of all elements of substring must be 0 or same with the one with odd occurrences. So we can use bitmasking to find the largest valid substring.

After then among all largest valid substrings we would generate the largest palindrome that are possible by rearranging the characters of the valid substring and keep track of the largest generated palindrome.

Follow the steps below to implement the above idea:

Initialize an array visited[] for storing the mask that has occurred previously
Iterate over the string:
- Calculate the current mask by toggling the corresponding bit of the current character in the string.
- Check if the mask is zero, which means the occurrence of all characters is even. So, this is a possible way to rearrange character to palindrome
  - Maximize the palindrome value.
- Toggle all possible bits one by one
  - Assign new mask = mask and toggle the corresponding bit in the new mask
  - Check if the new mask is zero, which means the occurrence of all characters is even except that one. So, this is a possible way to rearrange character to palindrome
    - Maximize the palindrome value in the result
  - Check if this new mask has occurred before
    - Maximize the palindrome value
- Check if the current mask is not been visited yet then, mark the current mask visited at index i.
Return the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum possible
// palindromic value
string maxValue(string& s, int i, int j)
{
    map<char, int> mp;
 
    for (int k = i; k <= j; k++) {
        mp[s[k]]++;
    }
 
    string res = "", oddChar = "";
 
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        if (it->second % 2 != 0) {
            oddChar = it->first;
        }
        else {
            res += string(it->second / 2, it->first);
        }
    }
 
    string reverseRes = res;
    reverse(reverseRes.begin(), reverseRes.end());
 
    string a = res + oddChar + reverseRes;
    return a;
}
 
// Function to find the maximum value
// between two given string
string maxOfBoth(string s1, string s2)
{
    if (s1.size() > s2.size())
        return s1;
    else if (s2.size() > s1.size())
        return s2;
 
    return ((s1 > s2) ? s1 : s2);
}
 
// Generate all possible valid palindrome
// and maximize the value among
// all palindrome
string maxPalindrome(string& s)
{
    // Initialize an array visited[] for
    // storing the mask that has occurred
    // previously
    vector<int> visited(5555, -1);
 
    int mask = 0, n = s.size();
    string result = "0";
 
    // Iterate over the string
    for (int i = 0; i < n; i++) {
 
        // Calculate the mask by toggling
        // the corresponding bit of current
        // character in the string.
        mask ^= (1 << (s[i] - '0'));
 
        // Check if mask is zero, means
        // occurrence of all character are
        // even. So, this is a possible
        // way to rearrange character
        // to palindrome
        if (mask == 0) {
 
            // Maximize the palindrome value
            result = maxOfBoth(result, maxValue(s, 0, i));
        }
 
        // Toggle all possible bit
        // one by one
        for (int j = 0; j <= 9; j++) {
 
            // Calculate the new Mask by
            // toggling the corresponding
            // bit of current mask
            int newMask = mask;
            newMask ^= (1 << j);
 
            // Check if mask is zero,
            // means occurrence of all
            // character are even except
            // one. So, this is a
            // possible way to rearrange
            // character to palindrome
            if (newMask == 0) {
 
                // Maximize the palindrome
                // value in result
                result
                    = maxOfBoth(result, maxValue(s, 0, i));
            }
 
            // Check if this new mask has
            // occurred before
            else if (visited[newMask] != -1) {
 
                // Maximize the palindrome
                // value
                result = maxOfBoth(
                    result,
                    maxValue(s, visited[newMask] + 1, i));
            }
        }
 
        // Check if the current mask is
        // not been visited yet
        // then, Mark the current mask
        // visited at index i
        if (visited[mask] == -1) {
            visited[mask] = i;
        }
    }
 
    // Return the result
    return result;
}
 
// Drive code
int main()
{
    string s = "25242459";
 
    // Function call
    cout << maxPalindrome(s);
 
    return 0;
}

Java

import java.util.*;
 
class Main
{
   
    // Function to find the maximum possible
    // palindromic value
    public static String maxValue(String s, int i, int j)
    {
        Map<Character, Integer> mp
            = new TreeMap<Character, Integer>(
                Collections.reverseOrder());
 
        for (int k = i; k <= j; k++) {
            if (mp.containsKey(s.charAt(k))) {
                mp.put(s.charAt(k),
                       mp.get(s.charAt(k)) + 1);
            }
            else {
                mp.put(s.charAt(k), 1);
            }
        }
        String res = "", oddChar = "";
        for (Map.Entry<Character, Integer> entry :
             mp.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                oddChar
                    = Character.toString(entry.getKey());
            }
            else {
                res += new String(
                           new char[entry.getValue() / 2])
                           .replace("\0",
                                    Character.toString(
                                        entry.getKey()));
            }
        }
        String reverseRes
            = new StringBuilder(res).reverse().toString();
        return res + oddChar + reverseRes;
    }
 
    // Function to find the maximum value
    // between two given string
    public static String maxOfBoth(String s1, String s2)
    {
        if (s1.length() > s2.length())
            return s1;
        else if (s2.length() > s1.length())
            return s2;
 
        return ((s1.compareTo(s2) > 0) ? s1 : s2);
    }
 
    // Generate all possible valid palindrome
    // and maximize the value among
    // all palindrome
    public static String maxPalindrome(String s)
    {
       
        // Initialize an array visited[] for
        // storing the mask that has occurred
        // previously
        int[] visited = new int[5555];
        Arrays.fill(visited, -1);
 
        int mask = 0, n = s.length();
        String result = "0";
 
        // Iterate over the string
        for (int i = 0; i < n; i++)
        {
           
            // Calculate the mask by toggling
            // the corresponding bit of current
            // character in the string.
            mask ^= (1 << (s.charAt(i) - '0'));
 
            // Check if mask is zero, means
            // occurrence of all character are
            // even. So, this is a possible
            // way to rearrange character
            // to palindrome
            if (mask == 0) 
            {
               
                // Maximize the palindrome value
                result
                    = maxOfBoth(result, maxValue(s, 0, i));
            }
 
            // Toggle all possible bit
            // one by one
            for (int j = 0; j <= 9; j++)
            {
               
                // Calculate the new Mask by
                // toggling the corresponding
                // bit of current mask
                int newMask = mask;
                newMask ^= (1 << j);
 
                // Check if mask is zero,
                // means occurrence of all
                // character are even except
                // one. So, this is a
                // possible way to rearrange
                // character to palindrome
                if (newMask == 0)
                {
                   
                    // Maximize the palindrome
                    // value in result
                    result = maxOfBoth(result,
                                       maxValue(s, 0, i));
                }
 
                // Check if this new mask has
                // occurred before
                else if (visited[newMask] != -1)
                {
                   
                    // Maximize the palindrome
                    // value
                    result = maxOfBoth(
                        result,
                        maxValue(s, visited[newMask] + 1,
                                 i));
                }
            }
           
            // Check if the current mask is
            // not been visited yet
            // then, Mark the current mask
            // visited at index i
            if (visited[mask] == -1) {
                visited[mask] = i;
            }
        }
       
        // Return the result
        return result;
    }
   
    // Driver code
    public static void main(String[] args)
    {
        String s = "25242459";
       
        // Function call
        System.out.println(maxPalindrome(s));
    }
}
 
// This code is contributed by Tapesh(tapeshdua420)

Python3

# Function to find the maximum possible
# palindromic value
def maxValue(s, i, j):
    mp = {}
 
    for k in range(i, j + 1):
        if s[k] not in mp:
            mp[s[k]] = 1
        else:
            mp[s[k]] += 1
 
    res = ""
    oddChar = ""
    for key in sorted(mp.keys(), reverse=True):
        if mp[key] % 2 != 0:
            oddChar = key
        else:
            res += (mp[key] // 2) * key
    reverseRes = res[::-1]
    a = res + oddChar + reverseRes
    return a
 
# Function to find the maximum value
# between two given string
def maxOfBoth(s1, s2):
    if len(s1) > len(s2):
        return s1
    elif len(s2) > len(s1):
        return s2
    else:
        return s1 if s1 > s2 else s2
 
# Generate all possible valid palindrome
# and maximize the value among
# all palindrome
def maxPalindrome(s):
    # Initialize an array visited[] for
    # storing the mask that has occurred
    # previously
    visited = [-1 for _ in range(5555)]
 
    mask = 0
    n = len(s)
    result = "0"
 
    # Iterate over the string
    for i in range(n):
        # Calculate the mask by toggling
        # the corresponding bit of current
        # character in the string.
        mask ^= (1 << (ord(s[i]) - ord('0')))
 
        # Check if mask is zero, means
        # occurrence of all character are
        # even. So, this is a possible
        # way to rearrange character
        # to palindrome
        if mask == 0:
            # Maximize the palindrome value
            result = maxOfBoth(result, maxValue(s, 0, i))
 
        # Toggle all possible bit
        # one by one
        for j in range(10):
            # Calculate the new Mask by
            # toggling the corresponding
            # bit of current mask
            newMask = mask ^ (1 << j)
 
            # Check if mask is zero,
            # means occurrence of all
            # character are even except
            # one. So, this is a
            # possible way to rearrange
            # character to palindrome
            if newMask == 0:
                # Maximize the palindrome
                # value in result
                result = maxOfBoth(result, maxValue(s, 0, i))
 
            # Check if this new mask has
            # occurred before
            elif visited[newMask] != -1:
                # Maximize the palindrome
                # value
                result = maxOfBoth(result, maxValue(
                    s, visited[newMask] + 1, i))
 
        # Check if the current mask is
        # not been visited yet
        # then, Mark the current mask
        # visited at index i
        if visited[mask] == -1:
            visited[mask] = i
 
    # Return the result
    return result
 
 
# Function call
print(maxPalindrome("25242459"))
 
# This code is contributed by Tapesh(tapeshdua420)

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program {
    // Function to find the maximum possible
    // palindromic value
    static string maxValue(string s, int i, int j)
    {
        var mp = new SortedDictionary<char, int>();
 
        for (int k = i; k <= j; k++) {
            if (mp.ContainsKey(s[k])) {
                mp[s[k]] += 1;
            }
            else {
                mp[s[k]] = 1;
            }
        }
 
        string res = "", oddChar = "";
 
        foreach(var entry in mp.Reverse())
        {
            if (entry.Value % 2 != 0) {
                oddChar = entry.Key.ToString();
            }
            else {
                res += new String(new char[entry.Value / 2])
                           .Replace("\0",
                                    entry.Key.ToString());
            }
        }
 
        string reverseRes
            = new string(res.Reverse().ToArray());
 
        return res + oddChar + reverseRes;
    }
 
    // Function to find the maximum value
    // between two given string
    static string maxOfBoth(string s1, string s2)
    {
 
        if (s1.Length > s2.Length)
            return s1;
        else if (s2.Length > s1.Length)
            return s2;
        return ((s1.CompareTo(s2) > 0) ? s1 : s2);
    }
 
    // Generate all possible valid palindrome
    // and maximize the value among
    // all palindrome
    static string maxPalindrome(string s)
    {
        // Initialize an array visited[] for
        // storing the mask that has occurred
        // previously
        int[] visited = new int[5555];
 
        for (int i = 0; i < visited.Length; i++)
            visited[i] = -1;
 
        int mask = 0, n = s.Length;
        string result = "0";
 
        // Iterate over the string
        for (int i = 0; i < n; i++) {
            // Calculate the mask by toggling
            // the corresponding bit of current
            // character in the string.
            mask ^= (1 << (s[i] - '0'));
 
            // Check if mask is zero, means
            // occurrence of all character are
            // even. So, this is a possible
            // way to rearrange character
            // to palindrome
            if (mask == 0)
                // Maximize the palindrome value
                result
                    = maxOfBoth(result, maxValue(s, 0, i));
 
            // Toggle all possible bit
            // one by one
            for (int j = 0; j <= 9; j++) {
                // Calculate the new Mask by
                // toggling the corresponding
                // bit of current mask
                int newMask = mask;
                newMask ^= (1 << j);
 
                // Check if mask is zero,
                // means occurrence of all
                // character are even except
                // one. So, this is a
                // possible way to rearrange
                // character to palindrome
                if (newMask == 0)
                    // Maximize the palindrome
                    // value in result
                    result = maxOfBoth(result,
                                       maxValue(s, 0, i));
                // Check if this new mask has
                // occurred before
                else if (visited[newMask] != -1)
                    // Maximize the palindrome
                    // value
                    result = maxOfBoth(
                        result,
                        maxValue(s, visited[newMask] + 1,
                                 i));
            }
            // Check if the current mask is
            // not been visited yet
            // then, Mark the current mask
            // visited at index i
            if (visited[mask] == -1)
                visited[mask] = i;
        }
        // Return the result
        return result;
    }
   
    // Driver code
    static void Main()
    {
        string s = "25242459";
        // Function call
        Console.WriteLine(maxPalindrome(s));
    }
}
// This code is contributed by Tapesh(tapeshdua420)

Javascript

// Function to find the maximum possible
// palindromic value
function maxValue(s, i, j) {
    var mp = {};
 
    for (var k = i; k <= j; k++) {
        if (mp[s[k]]) {
            mp[s[k]]++;
        } else {
            mp[s[k]] = 1;
        }
    }
    var items = Object.keys(mp).map(
      (key) => { return [key, mp[key]] });
 
    items.sort(
      (first, second) => { return second[0] - first[0] }
    );
 
    var res = "", oddChar = "";
    for (var it of items) {
        if (it[1] % 2 != 0) {
            oddChar = it[0];
        } else {
            res += new Array(it[1] / 2 + 1).join(it[0]);
        }
    }
    var reverseRes = res.split("").reverse().join("");
    return res + oddChar + reverseRes;
}
 
// Function to find the maximum value
// between two given string
function maxOfBoth(s1, s2) {
    if (s1.length > s2.length) {
        return s1;
    } else if (s2.length > s1.length) {
        return s2;
    } else {
        return (s1 > s2 ? s1 : s2);
    }
}
 
// Generate all possible valid palindrome
// and maximize the value among
// all palindrome
function maxPalindrome(s) {
    // Initialize an array visited[] for
    // storing the mask that has occurred
    // previously
    var visited = new Array(5555).fill(-1);
 
    var mask = 0;
    var n = s.length;
    var result = "0";
 
    // Iterate over the string
    for (var i = 0; i < n; i++) {
        // Calculate the mask by toggling
        // the corresponding bit of current
        // character in the string.
        mask ^= (1 << (s[i].charCodeAt() - '0'.charCodeAt()));
 
        // Check if mask is zero, means
        // occurrence of all character are
        // even. So, this is a possible
        // way to rearrange character
        // to palindrome
        if (mask == 0) {
 
            // Maximize the palindrome value
            result = maxOfBoth(result, maxValue(s, 0, i));
        }
 
        // Toggle all possible bit
        // one by one
        for (var j = 0; j < 10; j++) {
            // Calculate the new Mask by
            // toggling the corresponding
            // bit of current mask
            var newMask = mask ^ (1 << j);
 
            // Check if mask is zero,
            // means occurrence of all
            // character are even except
            // one. So, this is a
            // possible way to rearrange
            // character to palindrome
            if (newMask == 0) {
                // Maximize the palindrome
                // value in result
                result = maxOfBoth(result, maxValue(s, 0, i));
            } 
            // Check if this new mask has
            // occurred before
            else if (visited[newMask] != -1) {
                // Maximize the palindrome
                // value
                result = maxOfBoth(result, maxValue(s, visited[newMask] + 1, i));
            } 
        } 
        // Check if the current mask is
        // not been visited yet
        // then, Mark the current mask
        // visited at index i
        if (visited[mask] == -1) {
            visited[mask] = i;
        }
    }
    // Return the result
    return result;
}
 
// Function call
console.log(maxPalindrome("25242459"))
 
// This code is contributed by Tapesh(tapeshdua420)

Output

Time Complexity: O(N² * log(N))
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Strings

Related
Count odd length Substrings with median same as Kth character of String
Print Words with Prime length from a Sentence
How to insert characters in a string at a certain position?
Find Strings formed by replacing prefixes of given String with given characters
Make all Strings palindrome by swapping characters from adjacent Strings

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	14