Lexicographically smallest String by pair swapping
Suppose you are given a string Str of length N and a set of Pairs ( i, j such that 0 <= i < j < N, 0 based indexing). Pair “i, j” means that you can swap the ith and jth characters in the string any number of times. You have to output the lexicographically smallest string that can be produced by doing any number of swaps on the input string.
Examples:
Input: Str = zcxfbe Pairs = (0, 1), (0, 2), (3, 5)
Output: cxzebf
Explanation: First we will swap 0 and 2 char (new Str=xczfbe) then we will swap 0 and 1 char (new Str=cxzfbe) then we will swap 3 and 5 char (new Str=cxzebf).Input: Str = dcab Pairs = (0, 3), (1, 2)
Output: bacd
Explanation: First we will swap 0 and 3 char (new Str=bcad) then we will swap 2 and 1 char (new Str=bacd).
Efficient Approach: The approach is to find groups of characters that can be swapped together. We’ll use a graph to connect characters that can be swapped within each group. Here are the steps to follow this approach::
- Begin by creating N nodes to represent the string indexes.
- Connect these nodes based on the given pairs of characters.
- Group the connected nodes into disjoint sets, referred to as “Groups.”
- For each group, extract the characters from the input string corresponding to the group’s indices.
- Sort these extracted characters in lexicographical order.
- Reconstruct the final rearranged string by placing the sorted characters back into their original positions according to the indices.
Illustrations:
Below, you can find the representation of the string and the pairs of characters that can be swapped.
Next, we will construct a graph based on the relationships between pairs, which is depicted below.
Now, we will arrange each disconnected subgraph in lexicographically sorted order, as shown above.
Subsequently, we will reconstruct the string using the lexicographically sorted graph.
Below is the implementation of the above approach.
C++
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Graph { private : int V; vector<vector< int >> adj; public : // Constructor to initialize the graph with 'V' vertices Graph( int V) : V(V), adj(V) {} // Function to add a relationship (edge) between vertices 'v' and 'w' void addPair( int v, int w) { // Check if the indices are within bounds if (v >= 0 && v < V && w >= 0 && w < V) { // Adjust indices to be 0-based adj[v].push_back(w); adj[w].push_back(v); } else { cerr << "Invalid vertex indices: " << v << " or " << w << endl; } } // Utility function to perform depth-first traversal to find connected groups void countAll( int v, vector< int >& group, vector< bool >& visited) { visited[v] = true ; // Add the vertex to the current group (adjust index) group.push_back(v + 1); // Recursively explore neighbors of the current vertex for ( int neighbor : adj[v]) { if (!visited[neighbor]) { countAll(neighbor, group, visited); } } } // Function to find disjoint sets formed by the relations vector<vector< int >> disjointSets() { vector< bool > visited(V, false ); vector<vector< int >> all_sets; for ( int i = 0; i < V; ++i) { // If the vertex hasn't been visited, it's the start of a new group if (!visited[i]) { // Create a new group vector< int > group; // Find all vertices connected to this one countAll(i, group, visited); // Add the group to the list of all groups all_sets.push_back(group); } } return all_sets; } }; // Driver Code int main() { // Input string string Str = "zcxfbe" ; // Number of elements int N = 6; // Pairs of indices indicating relationships vector<vector< int >> Pairs = {{0, 1}, {0, 2}, {3, 5}}; // Create a graph with N vertices Graph g(N); // Add relations based on pairs for ( const auto & pair : Pairs) { g.addPair(pair[0], pair[1]); } // Find disjoint sets formed by the relations vector<vector< int >> disjoint_sets = g.disjointSets(); vector< int > key; vector< char > value; for ( size_t i = 0; i < disjoint_sets.size(); ++i) { // Temporary list to store characters within a group vector< char > semians; for ( int j : disjoint_sets[i]) { // Extract characters from the input string semians.push_back(Str[j - 1]); } // Sort the characters lexicographically sort(semians.begin(), semians.end()); // Sort the indices sort(disjoint_sets[i].begin(), disjoint_sets[i].end()); // Add sorted characters to the value list value.insert(value.end(), semians.begin(), semians.end()); // Add sorted indices to the key list key.insert(key.end(), disjoint_sets[i].begin(), disjoint_sets[i].end()); } // Initialize a list to reconstruct the final string vector< char > ans(N, ' ' ); // Reconstruct the final string based on sorted characters and indices for ( size_t i = 0; i < N; ++i) { ans[key[i] - 1] = value[i]; } // Print the rearranged string cout << string(ans.begin(), ans.end()) << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.Collections; import java.util.List; class Graph { private int V; private List<List<Integer>> adj; public Graph( int V) { this .V = V; adj = new ArrayList<>(V); for ( int i = 0 ; i < V; i++) { adj.add( new ArrayList<>()); } } public void addPair( int v, int w) { // Check if the indices are within bounds if (v >= 0 && v < V && w >= 0 && w < V) { adj.get(v).add(w); adj.get(w).add(v); } else { System.err.println( "Invalid vertex indices: " + v + " or " + w); } } public void countAll( int v, List<Integer> group, boolean [] visited) { visited[v] = true ; group.add(v + 1 ); for ( int neighbor : adj.get(v)) { if (!visited[neighbor]) { countAll(neighbor, group, visited); } } } public List<List<Integer>> disjointSets() { boolean [] visited = new boolean [V]; List<List<Integer>> allSets = new ArrayList<>(); for ( int i = 0 ; i < V; ++i) { if (!visited[i]) { List<Integer> group = new ArrayList<>(); countAll(i, group, visited); allSets.add(group); } } return allSets; } } public class Main { public static void main(String[] args) { String str = "zcxfbe" ; int N = 6 ; int [][] pairs = {{ 0 , 1 }, { 0 , 2 }, { 3 , 5 }}; Graph g = new Graph(N); // Add relations based on pairs for ( int [] pair : pairs) { g.addPair(pair[ 0 ], pair[ 1 ]); } List<List<Integer>> disjointSets = g.disjointSets(); List<Integer> key = new ArrayList<>(); List<Character> value = new ArrayList<>(); for ( int i = 0 ; i < disjointSets.size(); ++i) { List<Character> semians = new ArrayList<>(); for ( int j : disjointSets.get(i)) { semians.add(str.charAt(j - 1 )); } Collections.sort(semians); Collections.sort(disjointSets.get(i)); // Add sorted characters to the value list value.addAll(semians); // Add sorted indices to the key list key.addAll(disjointSets.get(i)); } char [] ans = new char [N]; for ( int i = 0 ; i < N; ++i) { ans[key.get(i) - 1 ] = value.get(i); } // Print the rearranged string System.out.println( new String(ans)); } } // This Code is contributed by Vikram_Shirsat |
Python
class Graph: def __init__( self , V): # Number of vertices in the graph self .V = V # Adjacency list to represent the graph self .adj = [[] for i in range (V)] def addPair( self , v, w): # Adjust indices to be 0-based v - = 1 w - = 1 # Add a relation (edge) between v and w self .adj[v].append(w) # Also add the reverse relation (undirected graph) self .adj[w].append(v) def disjointSets( self ): # Create a list to track visited vertices visited = [ False ] * self .V # List to store groups of connected vertices all_sets = [] def countAll(v, group): # Mark the current vertex as visited visited[v] = True # Add the vertex to the current group (adjust index) group.append(v + 1 ) # Recursively explore neighbors of the current vertex for neighbor in self .adj[v]: if not visited[neighbor]: countAll(neighbor, group) for i in range ( self .V): # If the vertex hasn't been visited, # it's the start of a new group if not visited[i]: # Create a new group group = [] # Find all vertices connected to this one countAll(i, group) # Add the group to the list of all groups all_sets.append(group) return all_sets # Driver Code # Input string Str = 'zcxfbe' # Number of elements N = 6 # Pairs of indices indicating relationships Pairs = [[ 0 , 1 ], [ 0 , 2 ], [ 3 , 5 ]] # Create a graph with N vertices g = Graph(N) # Add relations based on pairs for i in Pairs: g.addPair(i[ 0 ], i[ 1 ]) # Find groups formed by the relations groups = g.disjointSets() key = [] # List to store indices of characters value = [] # List to store characters # Sort characters within each group and store the results for i in range ( len (groups)): # Temporary list to store characters within a group semians = [] for j in groups[i]: # Extract characters from the input string semians.append( Str [j]) # Sort the characters lexicographically semians.sort() # Sort the indices groups[i].sort() # Add sorted characters to the value list value.extend(semians) # Add sorted indices to the key list key.extend(groups[i]) # Initialize a list to reconstruct the final string ans = [""] * N # Reconstruct the final string # based on sorted characters and indices for i in range (N): ans[key[i]] = value[i] # Print the rearranged string print (''.join(ans)) # This code is contributed by the Author |
C#
// C# IMplementation using System; using System.Collections.Generic; using System.Linq; class Graph { private int V; private List<List< int >> adj; public Graph( int V) { this .V = V; adj = new List<List< int >>(V); for ( int i = 0; i < V; i++) { adj.Add( new List< int >()); } } public void AddPair( int v, int w) { // Check if the indices are within bounds if (v >= 0 && v < V && w >= 0 && w < V) { adj[v].Add(w); adj[w].Add(v); } else { Console.WriteLine( "Invalid vertex indices: " + v + " or " + w); } } public void CountAll( int v, List< int > group , bool [] visited) { visited[v] = true ; group .Add(v + 1); foreach ( int neighbor in adj[v]) { if (!visited[neighbor]) { CountAll(neighbor, group , visited); } } } public List<List< int >> DisjointSets() { bool [] visited = new bool [V]; List<List< int >> allSets = new List<List< int >>(); for ( int i = 0; i < V; ++i) { if (!visited[i]) { List< int > group = new List< int >(); CountAll(i, group , visited); allSets.Add( group ); } } return allSets; } } public class MainClass { public static void Main( string [] args) { string str = "zcxfbe" ; int N = 6; int [][] pairs = { new int [] { 0, 1 }, new int [] { 0, 2 }, new int [] { 3, 5 } }; Graph g = new Graph(N); // Add relations based on pairs foreach ( int [] pair in pairs) { g.AddPair(pair[0], pair[1]); } List<List< int >> disjointSets = g.DisjointSets(); List< int > key = new List< int >(); List< char > value = new List< char >(); for ( int i = 0; i < disjointSets.Count; ++i) { List< char > semians = new List< char >(); foreach ( int j in disjointSets[i]) { semians.Add(str[j - 1]); } semians.Sort(); disjointSets[i].Sort(); // Add sorted characters to the value list value.AddRange(semians); // Add sorted indices to the key list key.AddRange(disjointSets[i]); } char [] ans = new char [N]; for ( int i = 0; i < N; ++i) { ans[key[i] - 1] = value[i]; } // Print the rearranged string Console.WriteLine( new string (ans)); } } // THis code is contributed by Sakshi |
Javascript
class GFG { constructor(V) { this .V = V; this .adj = new Array(V); for (let i = 0; i < V; i++) { this .adj[i] = []; } } addPair(v, w) { // Check if the indices are within bounds if (v >= 0 && v < this .V && w >= 0 && w < this .V) { this .adj[v].push(w); this .adj[w].push(v); } else { console.error( "Invalid vertex indices: " + v + " or " + w); } } countAll(v, group, visited) { visited[v] = true ; group.push(v + 1); for (let neighbor of this .adj[v]) { if (!visited[neighbor]) { this .countAll(neighbor, group, visited); } } } disjointSets() { const visited = new Array( this .V).fill( false ); const allSets = []; for (let i = 0; i < this .V; ++i) { if (!visited[i]) { const group = []; this .countAll(i, group, visited); allSets.push(group); } } return allSets; } } // Main function function main() { const str = "zcxfbe" ; const N = 6; const pairs = [[0, 1], [0, 2], [3, 5]]; const g = new GFG(N); // Add relations based on pairs for (const pair of pairs) { g.addPair(pair[0], pair[1]); } const disjointSets = g.disjointSets(); const key = []; const value = []; for (let i = 0; i < disjointSets.length; ++i) { const semians = []; for (const j of disjointSets[i]) { semians.push(str.charAt(j - 1)); } semians.sort(); disjointSets[i].sort(); // Add sorted characters to value list value.push(...semians); // Add sorted indices to key list key.push(...disjointSets[i]); } const ans = new Array(N); for (let i = 0; i < N; ++i) { ans[key[i] - 1] = value[i]; } // Print the rearranged string console.log(ans.join( '' )); } main(); |
cxzebf
Time Complexity: O(N log N),
Auxiliary Space: O(N), where N is the length of the input String.
Contact Us