Lexicographically Largest Substring having each Characters even times
Given a string S of length N (1 ≤ N ≤ 105) that consists of lowercase English letters. The task is to find a substring such that rearranging the characters within a substring makes it lexicographically the largest valid substring. A substring is invalid if all characters occur an even number of times, in case of no valid substring print -1.
Note: String “aaaa” is lexicographically the largest valid substring than string “zz” because of length(“aaaa”) > length(“zz”). whereas “zz” is lexicographically the largest valid substring than string “aa”.
Example:
Input: s = “bafbssbf”
Output: ssffbb
Explanation: The substring [2, 7] is a valid substring in which every character occurs even number of times, and “ssffbb” is the largest lexicographically string that is possible after rearranging the characters.Input: s = “abc”
Output: -1
Approach:
This problem can be solved using Hashing, as the even occurrences of characters can be calculated through frequency-counting. So we can use XOR operator to find out our resultant string.
- For even occurrence of every characters the XOR value of all characters of the valid substring must be 0. So we can use bitmasking to find the largest valid substring.
- In case XOR value is not 0 then we can check that if same XOR value had previously occurred before or not, if occurred then we can remove the previously occurred substring to make the XOR value 0.
- After then among all largest valid substrings we would generate the lexicographically largest substring by rearranging the characters.
Follow the steps below to implement the above idea:
- Initialize a map 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 current mask is zero, which means the occurrence of all characters is even.
- Maximize the value of this valid substring.
- Otherwise, Check if current mask has occurred before
- Maximize the value of this valid substring.
- 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 make lexicographically largest substring string maxValue(string& s, int i, int j) { string s1 = s.substr(i, j - i + 1); sort(s1.rbegin(), s1.rend()); return s1; } // Function to find the lexicographically largest valid // substring between two 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 substring // and maximize the value among // all valid substring string maxValidSubstring(string& s) { // Initilize a map for // storing the mask that has occured // previously unordered_map< long long , long long > visited; int mask = 0, n = s.size(); string result = "-1"; // 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] - 'a' )); // Check if mask is zero, means // occurance of all character are // even. if (mask == 0) { // Maximize the valid substring value result = maxOfBoth(result, maxValue(s, 0, i)); } // Check if this new mask has // occured before if (visited.find(mask) != visited.end()) { // Maximize the valid substring value result = maxOfBoth( result, maxValue(s, visited[mask] + 1, i)); } // Check if the current mask is // not been visited yet // then, Mark the current mask // visited at index i if (visited.find(mask) == visited.end()) { visited[mask] = i; } } // Return the result return result; } // Drive code int main() { string s = "bafbssbf"; // Function call cout << maxValidSubstring(s); return 0; } |
Java
import java.util.Arrays; import java.util.HashMap; public class MaxValidSubstring { // Function to make lexicographically largest substring static String maxValue(String s, int i, int j) { String s1 = s.substring(i, j + 1 ); char [] chars = s1.toCharArray(); Arrays.sort(chars); return new StringBuilder( new String(chars)).reverse().toString(); } // Function to find the lexicographically largest valid // substring between two strings 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 substrings // and maximize the value among // all valid substrings static String maxValidSubstring(String s) { HashMap<Long, Long> visited = new HashMap<>(); int mask = 0 , n = s.length(); String result = "-1" ; for ( int i = 0 ; i < n; i++) { mask ^= ( 1 << (s.charAt(i) - 'a' )); if (mask == 0 ) { result = maxOfBoth(result, maxValue(s, 0 , i)); } if (visited.containsKey(( long ) mask)) { result = maxOfBoth(result, maxValue(s, visited.get(( long ) mask).intValue() + 1 , i)); } if (!visited.containsKey(( long ) mask)) { visited.put(( long ) mask, ( long ) i); } } return result; } // Driver code public static void main(String[] args) { String s = "bafbssbf" ; // Function call System.out.println(maxValidSubstring(s)); } } |
Python
#Python code for the above approach: # Function to make lexicographically largest substring def max_value(s, i, j): s1 = s[i:j + 1 ] return ''.join( sorted (s1, reverse = True )) # Function to find the lexicographically largest valid # substring between two strings def max_of_both(s1, s2): if len (s1) > len (s2): return s1 elif len (s2) > len (s1): return s2 return s1 if s1 > s2 else s2 # Generate all possible valid substrings # and maximize the value among all valid substrings def max_valid_substring(s): # Initialize a dictionary for storing the mask that has occurred previously visited = {} mask = 0 result = "-1" # Iterate over the string for i in range ( len (s)): # Calculate the mask by toggling the corresponding bit of the current character in the string. mask ^ = ( 1 << ( ord (s[i]) - ord ( 'a' ))) # Check if mask is zero, means occurrence of all characters are even. if mask = = 0 : # Maximize the valid substring value result = max_of_both(result, max_value(s, 0 , i)) # Check if this new mask has occurred before if mask in visited: # Maximize the valid substring value result = max_of_both(result, max_value(s, visited[mask] + 1 , i)) # Check if the current mask has not been visited yet # then, mark the current mask visited at index i if mask not in visited: visited[mask] = i # Return the result return result # Main function if __name__ = = "__main__" : s = "bafbssbf" # Function call print (max_valid_substring(s)) # this code is contributed by uttamdp_10 |
C#
// C# Implementation using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to make lexicographically largest substring static string MaxValue( string s, int i, int j) { string s1 = s.Substring(i, j - i + 1); char [] chars = s1.ToCharArray(); Array.Sort(chars); Array.Reverse(chars); return new string (chars); } // Function to find the lexicographically largest valid // substring between two strings static string MaxOfBoth( string s1, string s2) { if (s1.Length > s2.Length) { return s1; } else if (s2.Length > s1.Length) { return s2; } return ( string .Compare(s1, s2) > 0) ? s1 : s2; } // Generate all possible valid substrings // and maximize the value among // all valid substrings static string MaxValidSubstring( string s) { Dictionary< long , long > visited = new Dictionary< long , long >(); int mask = 0, n = s.Length; string result = "-1" ; for ( int i = 0; i < n; i++) { mask ^= (1 << (s[i] - 'a' )); if (mask == 0) { result = MaxOfBoth(result, MaxValue(s, 0, i)); } if (visited.ContainsKey(( long )mask)) { result = MaxOfBoth(result, MaxValue(s, ( int )visited[( long )mask] + 1, i)); } if (!visited.ContainsKey(( long )mask)) { visited[( long )mask] = ( long )i; } } return result; } // Driver code public static void Main( string [] args) { string s = "bafbssbf" ; // Function call Console.WriteLine(MaxValidSubstring(s)); } } // This code is contributed by Sakshi |
Javascript
//Javascript Code // Function to make lexicographically largest substring function maxValue(s, i, j) { let s1 = s.substring(i, j + 1).split( '' ).sort((a, b) => b.localeCompare(a)).join( '' ); return s1; } // Function to find the lexicographically largest valid // substring between two strings function maxOfBoth(s1, s2) { if (s1.length > s2.length) return s1; else if (s2.length > s1.length) return s2; return (s1 > s2) ? s1 : s2; } // Generate all possible valid substrings // and maximize the value among all valid substrings function maxValidSubstring(s) { // Initilize a map for // storing the mask that has occured // previously let visited = new Map(); let mask = 0; let result = "-1" ; let n = s.length; // Iterate over the string for (let i = 0; i < n; i++) { // Calculate the mask by toggling // the corresponding bit of current // character in the string. mask ^= (1 << (s.charCodeAt(i) - 'a' .charCodeAt(0))); // Check if mask is zero, means // occurance of all character are // even. if (mask === 0) { // Maximize the valid substring value result = maxOfBoth(result, maxValue(s, 0, i)); } // Check if this new mask has // occured before if (visited.has(mask)) { // Maximize the valid substring value result = maxOfBoth(result, maxValue(s, visited.get(mask) + 1, i)); } // Check if the current mask is // not been visited yet // then, Mark the current mask // visited at index i if (!visited.has(mask)) { visited.set(mask, i); } } // Return the result return result; } // Drive code let s = "bafbssbf" ; // Function call console.log(maxValidSubstring(s)); |
ssffbb
Time Complexity: O(n log (n))
Auxiliary Space: O(n)