Given a string str and K pair of characters, the task is to check if string str can be made Palindrome, by replacing one character of each pair with the other.
Examples:
Input: str = “neveropen”, K = 2, pairs = [[“g”, “s”], [“k”, “e”]]
Output: True
Explanation:
Swap ‘s’ of “neveropen” with ‘g’ using pair [‘g’, ‘s’] = “geekg”
Swap ‘k’ of “geekg” with ‘e’ using pair [‘k’, ‘e’] = “geeeg”
Now the resultant string is a palindrome. Hence the output will be True.Input: str = “neveropen”, K = 1, pairs = [[“g”, “s”]]
Output: False
Explanation: Here only the first character can be swapped (g, s)
Final string formed will be : geekg, which is not a palindrome.
Naive Approach: The given problem can be solved by creating an undirected graph where an edge connecting (x, y) represents a relation between characters x and y.
- Check for the condition of palindrome by validating the first half characters with later half characters.
- If not equal:
- Run a dfs from the first character and check if the last character can be reached.
- Then, check for the second character with the second last character and so on.
Time Complexity: O(N * M), where N is size of target string and M is size of pairs array
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved efficiently with the help of following idea:
Use a disjoint set data structure where each pair [i][0] and pair [i][1] can be united under the same set and search operation can be done efficiently.
Instead of searching for the characters each time, try to group all the characters which are connected directly or indirectly, in the same set.
Below is the implementation of the above approach:
C++
#include <iostream> #include <string> #include <vector> using namespace std; // Structure for Disjoint set union struct disjoint_set { vector< int > parent, rank; // Initialize DSU variables disjoint_set() { parent.resize(26); rank.resize(26); for ( int i = 0 ; i < 26 ; i++) { parent[i] = i; rank[i] = 1; } } // Find parent of vertex 'v' int find_parent( int v) { if (v == parent[v]) return v; return parent[v] = find_parent(parent[v]); } // Union two sets containing vertices a and b void Union( int p1, int p2) { p1 = find_parent(p1); p2 = find_parent(p2); if (p1 != p2){ // rank of p1 smaller than p2 if (rank[p1] < rank[p2]){ parent[p1] = p2; } else if (rank[p2] < rank[p1]){ parent[p2] = p1; // rank of p2 equal to p1 } else { parent[p2] = p1; rank[p1] += 1; } } } // Function for checking whether // vertex a and b are in same set or not bool connected( int p1, int p2) { p1 = find_parent(p1); p2 = find_parent(p2); if (p1 == p2) return true ; return false ; } }; // Function solving the problem bool solve(string& target, vector<pair< char , char > >& pairs) { // Initialize new instance of DSU disjoint_set dsu; // Only lowercase letters for ( auto i : pairs) { dsu.Union(i.first - 'a' , i.second - 'a' ); } int lower = 0, upper = ( int )target.length() - 1; while (lower <= upper) { if (!dsu.connected(target[lower] - 'a' , target[upper] - 'a' )) { return false ; } lower+=1; upper-=1; } return true ; } // Driver code int main() { string target = "neveropen" ; vector<pair< char , char > > pairs = { { 'g' , 's' }, { 'e' , 'k' } }; bool ans = solve(target, pairs); if (ans) { cout << "true\n" ; } else { cout << "false\n" ; } return 0; } // This code is contributed by subhamgoyal2014. |
Python3
# Python code for the above approach: class disjoint_set(): def __init__( self ): # string consist of only smallcase letters self .parent = [i for i in range ( 26 )] self .rank = [ 1 for i in range ( 26 )] def find_parent( self , x): if ( self .parent[x] = = x): return x self .parent[x] = self .find_parent( self .parent[x]) return ( self .parent[x]) def union( self , u, v): p1 = self .find_parent(u) p2 = self .find_parent(v) if (p1 ! = p2): # rank of p1 smaller than p2 if ( self .rank[p1] < self .rank[p2]): self .parent[p1] = p2 elif ( self .rank[p2] < self .rank[p1]): self .parent[p2] = p1 # rank of p2 equal to p1 else : self .parent[p2] = p1 self .rank[p1] + = 1 def connected( self , w1, w2): p1 = self .find_parent(w1) p2 = self .find_parent(w2) if (p1 = = p2): return True return False class Solution: def solve( self , target, pairs): size = len (target) # Create a object of disjoint set dis_obj = disjoint_set() for (u, v) in pairs: ascii_1 = ord (u) - ord ( 'a' ) ascii_2 = ord (v) - ord ( 'a' ) # Take union of both the characters dis_obj.union(ascii_1, ascii_2) left = 0 right = size - 1 # Check for palindrome condition # For every character while (left < right): s1 = target[left] s2 = target[right] # If characters not same if (s1 ! = s2): # Convert to ascii value between 0-25 ascii_1 = ord (s1) - ord ( 'a' ) ascii_2 = ord (s2) - ord ( 'a' ) # Check if both the words # Belong to same set if ( not dis_obj.connected(ascii_1, ascii_2)): return False left + = 1 right - = 1 # Finally return True return ( True ) if __name__ = = '__main__' : target = "neveropen" pairs = [[ "g" , "s" ], [ "e" , "k" ]] obj = Solution() ans = obj.solve(target, pairs) if (ans): print ( 'true' ) else : print ( 'false' ) |
C#
using System; using System.Collections.Generic; class Program { // Structure for Disjoint set union private class DisjointSet { private int [] parent, rank; // Initialize DSU variables public DisjointSet() { parent = new int [26]; rank = new int [26]; for ( int i = 0; i < 26; i++) { parent[i] = i; rank[i] = 1; } } // Find parent of vertex 'v' public int FindParent( int v) { if (v == parent[v]) return v; return parent[v] = FindParent(parent[v]); } // Union two sets containing vertices a and b public void Union( int p1, int p2) { p1 = FindParent(p1); p2 = FindParent(p2); if (p1 != p2) { // rank of p1 smaller than p2 if (rank[p1] < rank[p2]) { parent[p1] = p2; } else if (rank[p2] < rank[p1]) { parent[p2] = p1; } // rank of p2 equal to p1 else { parent[p2] = p1; rank[p1] += 1; } } } // Function for checking whether // vertex a and b are in same set or not public bool Connected( int p1, int p2) { p1 = FindParent(p1); p2 = FindParent(p2); if (p1 == p2) return true ; return false ; } } // Function solving the problem private static bool Solve( string target, List<Tuple< char , char >> pairs) { // Initialize new instance of DSU DisjointSet dsu = new DisjointSet(); // Only lowercase letters foreach ( var i in pairs) { dsu.Union(i.Item1 - 'a' , i.Item2 - 'a' ); } int lower = 0, upper = target.Length - 1; while (lower <= upper) { if (!dsu.Connected(target[lower] - 'a' , target[upper] - 'a' )) { return false ; } lower += 1; upper -= 1; } return true ; } // Driver code static void Main( string [] args) { string target = "neveropen" ; List<Tuple< char , char >> pairs = new List<Tuple< char , char >>() { new Tuple< char , char >( 'g' , 's' ), new Tuple< char , char >( 'e' , 'k' ) }; bool ans = Solve(target, pairs); if (ans) { Console.WriteLine( "true" ); } else { Console.WriteLine( "false" ); } } } // This code is contributed by lokeshpotta20. |
Java
import java.util.*; public class GFG { // Structure for Disjoint set union public static class DisjointSet { private int [] parent, rank; // Initialize DSU variables public DisjointSet() { parent = new int [ 26 ]; rank = new int [ 26 ]; for ( int i = 0 ; i < 26 ; i++) { parent[i] = i; rank[i] = 1 ; } } // Find parent of vertex 'v' public int findParent( int v) { if (v == parent[v]) return v; return parent[v] = findParent(parent[v]); } // Union two sets containing vertices a and b public void union( int p1, int p2) { p1 = findParent(p1); p2 = findParent(p2); if (p1 != p2) { // rank of p1 smaller than p2 if (rank[p1] < rank[p2]) { parent[p1] = p2; } else if (rank[p2] < rank[p1]) { parent[p2] = p1; } // rank of p2 equal to p1 else { parent[p2] = p1; rank[p1] += 1 ; } } } // Function for checking whether // vertex a and b are in same set or not public boolean connected( int p1, int p2) { p1 = findParent(p1); p2 = findParent(p2); if (p1 == p2) return true ; return false ; } } // Function solving the problem public static boolean solve(String target, List<Map.Entry<Character, Character>> pairs) { // Initialize new instance of DSU DisjointSet dsu = new DisjointSet(); // Only lowercase letters for (Map.Entry<Character, Character> i : pairs) { dsu.union(i.getKey() - 'a' , i.getValue() - 'a' ); } int lower = 0 , upper = target.length() - 1 ; while (lower <= upper) { if (!dsu.connected(target.charAt(lower) - 'a' , target.charAt(upper) - 'a' )) { return false ; } lower += 1 ; upper -= 1 ; } return true ; } // Driver code public static void main(String[] args) { String target = "neveropen" ; List<Map.Entry<Character, Character>> pairs = new ArrayList<>(); pairs.add( new AbstractMap.SimpleEntry<>( 'g' , 's' )); pairs.add( new AbstractMap.SimpleEntry<>( 'e' , 'k' )); boolean ans = solve(target, pairs); if (ans) { System.out.println( "true" ); } else { System.out.println( "false" ); } } } |
Javascript
<script> // JavaScript code for the above approach: class disjoint_set{ constructor(){ // string consist of only smallcase letters this .parent = new Array(26) for (let i=0;i<26;i++){ this .parent[i] = i } this .rank = new Array(26).fill(1) } find_parent(x){ if ( this .parent[x] == x) return x this .parent[x] = this .find_parent( this .parent[x]) return ( this .parent[x]) } union(u, v){ let p1 = this .find_parent(u) let p2 = this .find_parent(v) if (p1 != p2){ // rank of p1 smaller than p2 if ( this .rank[p1] < this .rank[p2]) this .parent[p1] = p2 else if ( this .rank[p2] < this .rank[p1]) this .parent[p2] = p1 // rank of p2 equal to p1 else { this .parent[p2] = p1 this .rank[p1] += 1 } } } connected(w1, w2){ let p1 = this .find_parent(w1) let p2 = this .find_parent(w2) if (p1 == p2) return true return false } } class Solution{ solve(target, pairs){ let size = target.length // Create a object of disjoint set let dis_obj = new disjoint_set() for (let [u, v] of pairs){ let ascii_1 = (u).charCodeAt(0) - ( 'a' ).charCodeAt(0) let ascii_2 = (v).charCodeAt(0) - ( 'a' ).charCodeAt(0) // Take union of both the characters dis_obj.union(ascii_1, ascii_2) } let left = 0 let right = size-1 // Check for palindrome condition // For every character while (left < right){ let s1 = target[left] let s2 = target[right] // If characters not same if (s1 != s2){ // Convert to ascii value between 0-25 let ascii_1 = s1.charCodeAt(0) - 'a' .charCodeAt(0) let ascii_2 = s2.charCodeAt(0) - 'a' .charCodeAt(0) // Check if both the words // Belong to same set if (!dis_obj.connected(ascii_1, ascii_2)) return false } left += 1 right -= 1 } // Finally return true return true } } // driver code let target = "neveropen" let pairs = [[ "g" , "s" ], [ "e" , "k" ]] let obj = new Solution() let ans = obj.solve(target, pairs) if (ans) document.write( 'true' ) else document.write( 'false' ) // This code is contributed by shinjanpatra </script> |
true
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!