Given a string S, the task is to find the minimum length string such that every adjacent character of the string remains adjacent in the minimum length string.
Examples:
Input: S = “acabpba”
Output: pbac
Explanation:
The given string can be converted to “pbac” in which,
every adjacent character remains adjacent.Input: S = “abcdea”
Output: Impossible
Explanation:
It is impossible to find such string.
Approach: The idea is to prepare a graph like structure in which every adjacent nodes of the graph denotes the adjacent character of the string. There can be two cases in which such type of string is not possible –
- If a character contains three or more adjacent characters.
- If two characters do not have only one adjacent character, except in the case of string of length 1.
If the above conditions for a string are true, then simply traverse the graph with Depth First Search Traversal and the path of this traversal will be the minimum length string. Source vertex for the DFS will be any one of the characters with only one adjacent character.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // minimum length string such that // adjacent characters of the string // remains adjacent in the string #include <bits/stdc++.h> using namespace std; class graph { int arr[26][2]; vector< int > alpha; vector< int > answer; public : // Constructor for the graph graph() { // Initialize the matrix by -1 for ( int i = 0; i < 26; i++) { for ( int j = 0; j < 2; j++) arr[i][j] = -1; } // Initialize the alphabet array alpha = vector< int >(26); } // Function to do Depth first // search Traversal void dfs( int v) { // Pushing current character answer.push_back(v); alpha[v] = 1; for ( int i = 0; i < 2; i++) { if (alpha[arr[v][i]] == 1 || arr[v][i] == -1) continue ; dfs(arr[v][i]); } } // Function to find the minimum // length string void minString(string str) { // Condition if given string // length is 1 if (str.length() == 1) { cout << str << "\n" ; return ; } bool flag = true ; // Loop to find the adjacency // list of the given string for ( int i = 0; i < str.length() - 1; i++) { int j = str[i] - 'a' ; int k = str[i + 1] - 'a' ; // Condition if character // already present if (arr[j][0] == k || arr[j][1] == k) { } else if (arr[j][0] == -1) arr[j][0] = k; else if (arr[j][1] == -1) arr[j][1] = k; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } if (arr[k][0] == j || arr[k][1] == j) { } else if (arr[k][0] == -1) arr[k][0] = j; else if (arr[k][1] == -1) arr[k][1] = j; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } } // Variable to check string contain // two end characters or not bool contain_ends = false ; int count = 0; int index; for ( int i = 0; i < 26; i++) { // Condition if a character has // only one type of adjacent // character if ((arr[i][0] == -1 && arr[i][1] != -1) || (arr[i][1] == -1 && arr[i][0] != -1)) { count++; index = i; } // Condition if the given string // has exactly two characters // having only one type of adjacent // character if (count == 2) contain_ends = true ; if (count == 3) contain_ends = false ; } if (contain_ends == false || flag == false ) { cout << "Impossible" << "\n" ; return ; } // Depth first Search Traversal // on one of the possible end // character of the string dfs(index); // Loop to print the answer for ( int i = 0; i < answer.size(); i++) { char ch = answer[i] + 'a' ; cout << ch; } } }; // Driver Code int main() { string s = "acabpba" ; graph g; g.minString(s); return 0; } |
Java
// Java implementation to find the // minimum length string such that // adjacent characters of the string // remains adjacent in the string import java.util.ArrayList; class Graph{ int [][] arr; ArrayList<Integer> alpha; ArrayList<Integer> answer; // Constructor for the Graph public Graph() { arr = new int [ 26 ][ 2 ]; // Initialize the matrix by -1 for ( int i = 0 ; i < 26 ; i++) { for ( int j = 0 ; j < 2 ; j++) arr[i][j] = - 1 ; } // Initialize the alphabet array alpha = new ArrayList<>(); for ( int i = 0 ; i < 26 ; i++) { alpha.add( 0 ); } answer = new ArrayList<>(); } // Function to do Depth first // search Traversal void dfs( int v) { // Pushing current character answer.add(v); alpha.set(v, 1 ); for ( int i = 0 ; i < 2 ; i++) { if (arr[v][i] == - 1 || alpha.get(arr[v][i]) == 1 ) continue ; dfs(arr[v][i]); } } // Function to find the minimum // length string void minString(String str) { // Condition if given string // length is 1 if (str.length() == 1 ) { System.out.println(str); return ; } boolean flag = true ; // Loop to find the adjacency // list of the given string for ( int i = 0 ; i < str.length() - 1 ; i++) { int j = str.charAt(i) - 'a' ; int k = str.charAt(i + 1 ) - 'a' ; // Condition if character // already present if (arr[j][ 0 ] == k || arr[j][ 1 ] == k) {} else if (arr[j][ 0 ] == - 1 ) arr[j][ 0 ] = k; else if (arr[j][ 1 ] == - 1 ) arr[j][ 1 ] = k; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } if (arr[k][ 0 ] == j || arr[k][ 1 ] == j) {} else if (arr[k][ 0 ] == - 1 ) arr[k][ 0 ] = j; else if (arr[k][ 1 ] == - 1 ) arr[k][ 1 ] = j; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } } // Variable to check string contain // two end characters or not boolean contain_ends = false ; int count = 0 ; int index = 0 ; for ( int i = 0 ; i < 26 ; i++) { // Condition if a character has // only one type of adjacent // character if ((arr[i][ 0 ] == - 1 && arr[i][ 1 ] != - 1 ) || (arr[i][ 1 ] == - 1 && arr[i][ 0 ] != - 1 )) { count++; index = i; } // Condition if the given string // has exactly two characters // having only one type of adjacent // character if (count == 2 ) contain_ends = true ; if (count == 3 ) contain_ends = false ; } if (contain_ends == false || flag == false ) { System.out.println( "Impossible" ); return ; } // Depth first Search Traversal // on one of the possible end // character of the string dfs(index); // Loop to print the answer for ( int i = 0 ; i < answer.size(); i++) { char ch = ( char )(answer.get(i) + 'a' ); System.out.print(ch); } } } class GFG{ // Driver Code public static void main(String[] args) { String s = "acabpba" ; Graph graph = new Graph(); graph.minString(s); } } // This code is contributed by sanjeev2552 |
Python3
# Python implementation to find the # minimum length string such that # adjacent characters of the string # remains adjacent in the string # Initialize the matrix by -1 arr = [[ - 1 for i in range ( 2 )] for j in range ( 26 )] # Initialize the alphabet array alpha = [ 0 for i in range ( 26 )] answer = [] # Function to do Depth first # search Traversal def dfs(v): global arr global alpha global answer # Pushing current character answer.append(v) alpha[v] = 1 for i in range ( 2 ): if (alpha[arr[v][i]] = = 1 or arr[v][i] = = - 1 ): continue dfs(arr[v][i]) # Function to find the minimum # length string def minString( Str ): # Condition if given string # length is 1 if ( len ( Str ) = = 1 ): print ( Str ) return flag = True temp = 0 # Loop to find the adjacency # list of the given string for i in range ( 0 , len ( Str ) - 1 ): j = ord ( Str [i]) - ord ( 'a' ) k = ord ( Str [i + 1 ]) - ord ( 'a' ) # Condition if character # already present we can do nothing if (arr[j][ 0 ] = = k or arr[j][ 1 ] = = k): temp = 1 elif (arr[j][ 0 ] = = - 1 ): arr[j][ 0 ] = k elif (arr[j][ 1 ] = = - 1 ): arr[j][ 1 ] = k # Condition if a character # have more than two different # adjacent characters else : flag = alse break if (arr[k][ 0 ] = = j or arr[k][ 1 ] = = j): temp = 0 elif (arr[k][ 0 ] = = - 1 ): arr[k][ 0 ] = j elif (arr[k][ 1 ] = = - 1 ): arr[k][ 1 ] = j # Condition if a character # have more than two different # adjacent characters else : flag = False break # Variable to check string contain # two end characters or not contain_ends = False count = 0 index = 0 for i in range ( 26 ): # Condition if a character has # only one type of adjacent # character if ((arr[i][ 0 ] = = - 1 and arr[i][ 1 ] ! = - 1 ) or (arr[i][ 1 ] = = - 1 and arr[i][ 0 ] ! = - 1 )): count + = 1 index = i # Condition if the given string # has exactly two characters # having only one type of adjacent # character if (count = = 2 ): contain_ends = True if (count = = 3 ): contain_ends = False if (contain_ends = = False or flag = = False ): print ( "Impossible" ) return # Depth first Search Traversal # on one of the possible end # character of the string dfs(index) # Loop to print the answer for i in range ( len (answer)): ch = chr (answer[i] + ord ( 'a' )) print (ch, end = "") # Driver Code s = "acabpba" minString(s) # This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript implementation to find the // minimum length string such that // adjacent characters of the string // remains adjacent in the string let arr; let alpha; let answer; // Constructor for the Graph function Graph() { arr = new Array(26); for (let i = 0; i < 26; i++) { arr[i] = new Array(2); for (let j = 0; j < 2; j++) arr[i][j] = -1; } alpha = []; for (let i = 0; i < 26; i++) { alpha.push(0); } answer = []; } // Function to do Depth first // search Traversal function dfs(v) { // Pushing current character answer.push(v); alpha[v]= 1; for (let i = 0; i < 2; i++) { if (arr[v][i] == -1 || alpha[arr[v][i]] == 1) continue ; dfs(arr[v][i]); } } // Function to find the minimum // length string function minString(str) { // Condition if given string // length is 1 if (str.length == 1) { document.write(str+ "<br>" ); return ; } let flag = true ; // Loop to find the adjacency // list of the given string for (let i = 0; i < str.length - 1; i++) { let j = str[i].charCodeAt(0) - 'a' .charCodeAt(0); let k = str[i + 1].charCodeAt(0) - 'a' .charCodeAt(0); // Condition if character // already present if (arr[j][0] == k || arr[j][1] == k) {} else if (arr[j][0] == -1) arr[j][0] = k; else if (arr[j][1] == -1) arr[j][1] = k; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } if (arr[k][0] == j || arr[k][1] == j) {} else if (arr[k][0] == -1) arr[k][0] = j; else if (arr[k][1] == -1) arr[k][1] = j; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } } // Variable to check string contain // two end characters or not let contain_ends = false ; let count = 0; let index = 0; for (let i = 0; i < 26; i++) { // Condition if a character has // only one type of adjacent // character if ((arr[i][0] == -1 && arr[i][1] != -1) || (arr[i][1] == -1 && arr[i][0] != -1)) { count++; index = i; } // Condition if the given string // has exactly two characters // having only one type of adjacent // character if (count == 2) contain_ends = true ; if (count == 3) contain_ends = false ; } if (contain_ends == false || flag == false ) { document.write( "Impossible<br>" ); return ; } // Depth first Search Traversal // on one of the possible end // character of the string dfs(index); // Loop to print the answer for (let i = 0; i < answer.length; i++) { let ch = String.fromCharCode(answer[i] + 'a' .charCodeAt(0)); document.write(ch); } } // Driver Code let s = "acabpba" ; Graph(); minString(s); // This code is contributed by ab2127 </script> |
C#
using System.Collections.Generic; using System; class Graph{ int [,] arr; List< int > alpha; List< int > answer; // Constructor for the Graph public Graph() { arr = new int [26,2]; // Initialize the matrix by -1 for ( int i = 0; i < 26; i++) { for ( int j = 0; j < 2; j++) arr[i,j] = -1; } // Initialize the alphabet array alpha = new List< int >(); for ( int i = 0; i < 26; i++) { alpha.Add(0); } answer = new List< int >(); } // Function to do Depth first // search Traversal void dfs( int v) { // Pushing current character answer.Add(v); alpha[v] = 1; for ( int i = 0; i < 2; i++) { if (arr[v,i] == -1 || alpha[arr[v,i]] == 1) continue ; dfs(arr[v,i]); } } // Function to find the minimum // length string public void minString( string str) { // Condition if given string // length is 1 if (str.Length == 1) { Console.WriteLine(str); return ; } bool flag = true ; // Loop to find the adjacency // list of the given string for ( int i = 0; i < str.Length - 1; i++) { int j = str[i] - 'a' ; int k = str[i+1] - 'a' ; // Condition if character // already present if (arr[j,0] == k || arr[j,1] == k) {} else if (arr[j,0] == -1) arr[j,0] = k; else if (arr[j,1] == -1) arr[j,1] = k; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } if (arr[k,0] == j || arr[k,1] == j) {} else if (arr[k,0] == -1) arr[k,0] = j; else if (arr[k,1] == -1) arr[k,1] = j; // Condition if a character // have more than two different // adjacent characters else { flag = false ; break ; } } // Variable to check string contain // two end characters or not bool contain_ends = false ; int count = 0; int index = 0; for ( int i = 0; i < 26; i++) { // Condition if a character has // only one type of adjacent // character if ((arr[i,0] == -1 && arr[i,1] != -1) || (arr[i,1] == -1 && arr[i,0] != -1)) { count++; index = i; } // Condition if the given string // has exactly two characters // having only one type of adjacent // character if (count == 2) contain_ends = true ; if (count == 3) contain_ends = false ; } if (contain_ends == false || flag == false ) { Console.WriteLine( "Impossible" ); return ; } // Depth first Search Traversal // on one of the possible end // character of the string dfs(index); // Loop to print the answer for ( int i = 0; i < answer.Count; i++) { char ch = ( char )(answer[i] + 'a' ); Console.Write(ch); } } } // Driver Code public class GFG{ static public void Main (){ string s = "acabpba" ; Graph graph = new Graph(); graph.minString(s); } } // This code is contributed by patel2127. |
pbac
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!