Two-Color Sorting
Given a string s consisting of n lowercase letters. You have to color all of its characters using two colors such that each index of s is assigned exactly one color. You can swap two adjacent indexes of s that have different colors any number of times. The task is to determine whether you can sort the strings or not.
Examples:
Input: n = 9, s = abacbecfd
Output: YES
001010101Input: 8, s = aaabbcbb
Output: YES
01011011
Approach: To solve the problem follow the below idea:
The idea is to use dynamic programming to determine if it is possible to color a given string such that, through swaps of adjacent differently colored characters, the string becomes sorted. It assigns colors based on the alphabetical order, considering adjacent characters and their possible colorings, and then reconstructs the valid coloring by backtracking from the last character. The final result indicates whether sorting is achievable, and if so, provides a valid coloring of the string.
Step-by-step approach:
- Initialize a dynamic programming array dp to track the possibility of achieving the desired coloring.
- Set the initial state for an empty string as valid (dp[0][0][0] = 1).
- Iterate through each character of the string.
- For each character, iterate over possible colors for adjacent characters and update the dynamic programming array based on conditions.
- Find the last character’s valid coloring by checking the final dynamic programming states.
- Reconstruct the valid coloring of the string by backtracking from the last character to the first.
- Store the colors and the corresponding swaps in a result string.
- If no valid coloring is found, output “NO.”
- If a valid coloring is found, output “YES” and the reconstructed coloring.
Below is the implementation of the above approach:
C++14
#include <bits/stdc++.h> using namespace std; const int MaxLength = 222; // Maximum length of the string const int AlphabetSize = 26; // Size of the Latin alphabet bool dp[MaxLength][AlphabetSize][AlphabetSize]; pair<pair< int , int >, int > parent[MaxLength][AlphabetSize] [AlphabetSize]; int main() { int n = 9; string s = "abacbecfd"; // Dynamic programming initialization dp[0][0][0] = 1; for ( int i = 0; i < n; ++i) { int currentChar = s[i] - 'a' ; // Iterate over possible colors for adjacent // characters for ( int color1 = 0; color1 < AlphabetSize; ++color1) { for ( int color2 = 0; color2 < AlphabetSize; ++color2) { if (!dp[i][color1][color2]) continue ; // Check conditions for assigning colors and // update DP states if (currentChar >= color1) { dp[i + 1][currentChar][color2] = 1; parent[i + 1][currentChar][color2] = make_pair( make_pair(color1, color2), 0); } if (currentChar >= color2) { dp[i + 1][color1][currentChar] = 1; parent[i + 1][color1][currentChar] = make_pair( make_pair(color1, color2), 1); } } } } int lastColor1 = -1, lastColor2 = -1; // Find possible colors for the last character for ( int color1 = 0; color1 < AlphabetSize; ++color1) { for ( int color2 = 0; color2 < AlphabetSize; ++color2) { if (dp[n][color1][color2]) { lastColor1 = color1; lastColor2 = color2; } } } // If no valid colors found, print "NO" if (lastColor1 == -1) { cout << "NO" << endl; return 0; } // Reconstruct the coloring string coloring; for ( int i = n; i > 0; --i) { int prevColor1 = parent[i][lastColor1][lastColor2].first.first; int prevColor2 = parent[i][lastColor1][lastColor2] .first.second; if (parent[i][lastColor1][lastColor2].second) { coloring += '1' ; } else { coloring += '0' ; } lastColor1 = prevColor1; lastColor2 = prevColor2; } reverse(coloring.begin(), coloring.end()); // Print the result cout << "YES" << endl << coloring << endl; return 0; } |
Java
import java.util.*; public class ColoringString { static final int MaxLength = 222 ; static final int AlphabetSize = 26 ; static boolean [][][] dp = new boolean [MaxLength][AlphabetSize] [AlphabetSize]; static int [][][] parent = new int [MaxLength][AlphabetSize][AlphabetSize]; public static void main(String[] args) { int n = 9 ; String s = "abacbecfd" ; // Dynamic programming initialization dp[ 0 ][ 0 ][ 0 ] = true ; for ( int i = 0 ; i < n; ++i) { int currentChar = s.charAt(i) - 'a' ; // Iterate over possible colors for adjacent // characters for ( int color1 = 0 ; color1 < AlphabetSize; ++color1) { for ( int color2 = 0 ; color2 < AlphabetSize; ++color2) { if (!dp[i][color1][color2]) continue ; // Check conditions for assigning colors // and update DP states if (currentChar >= color1) { dp[i + 1 ][currentChar][color2] = true ; parent[i + 1 ][currentChar][color2] = color1; } if (currentChar >= color2) { dp[i + 1 ][color1][currentChar] = true ; parent[i + 1 ][color1][currentChar] = color2 + AlphabetSize; } } } } int lastColor1 = - 1 , lastColor2 = - 1 ; // Find possible colors for the last character for ( int color1 = 0 ; color1 < AlphabetSize; ++color1) { for ( int color2 = 0 ; color2 < AlphabetSize; ++color2) { if (dp[n][color1][color2]) { lastColor1 = color1; lastColor2 = color2; } } } // If no valid colors found, print "NO" if (lastColor1 == - 1 ) { System.out.println( "NO" ); return ; } // Reconstruct the coloring StringBuilder coloring = new StringBuilder(); for ( int i = n; i > 0 ; --i) { int prevColor = parent[i][lastColor1][lastColor2]; if (prevColor >= AlphabetSize) { coloring.append( '1' ); lastColor2 = prevColor - AlphabetSize; } else { coloring.append( '0' ); lastColor1 = prevColor; } } coloring.reverse(); // Print the result System.out.println( "YES" ); System.out.println(coloring); } } |
Python3
MaxLength = 222 # Maximum length of the string AlphabetSize = 26 # Size of the Latin alphabet # Dynamic programming initialization dp = [[[ False for _ in range (AlphabetSize)] for _ in range (AlphabetSize)] for _ in range (MaxLength)] parent = [[[[( 0 , 0 ), 0 ] for _ in range (AlphabetSize)] for _ in range (AlphabetSize)] for _ in range (MaxLength)] n = 9 s = "abacbecfd" # Initialize DP dp[ 0 ][ 0 ][ 0 ] = True for i in range (n): currentChar = ord (s[i]) - ord ( 'a' ) # Iterate over possible colors for adjacent characters for color1 in range (AlphabetSize): for color2 in range (AlphabetSize): if not dp[i][color1][color2]: continue # Check conditions for assigning colors and update DP states if currentChar > = color1: dp[i + 1 ][currentChar][color2] = True parent[i + 1 ][currentChar][color2] = ((color1, color2), 0 ) if currentChar > = color2: dp[i + 1 ][color1][currentChar] = True parent[i + 1 ][color1][currentChar] = ((color1, color2), 1 ) lastColor1, lastColor2 = - 1 , - 1 # Find possible colors for the last character for color1 in range (AlphabetSize): for color2 in range (AlphabetSize): if dp[n][color1][color2]: lastColor1, lastColor2 = color1, color2 # If no valid colors found, print "NO" if lastColor1 = = - 1 : print ( "NO" ) else : # Reconstruct the coloring coloring = "" for i in range (n, 0 , - 1 ): prevColor1, prevColor2 = parent[i][lastColor1][lastColor2][ 0 ] if parent[i][lastColor1][lastColor2][ 1 ]: coloring + = '1' else : coloring + = '0' lastColor1, lastColor2 = prevColor1, prevColor2 # Print the result print ( "YES" ) print (coloring[:: - 1 ]) |
C#
using System; class Program { const int MaxLength = 222; // Maximum length of the string const int AlphabetSize = 26; // Size of the Latin alphabet static bool [,,] dp = new bool [MaxLength, AlphabetSize, AlphabetSize]; static Tuple<Tuple< int , int >, int >[,,] parent = new Tuple<Tuple< int , int >, int >[MaxLength, AlphabetSize, AlphabetSize]; static void Main() { int n = 9; string s = "abacbecfd" ; // Dynamic programming initialization dp[0, 0, 0] = true ; for ( int i = 0; i < n; ++i) { int currentChar = s[i] - 'a' ; // Iterate over possible colors for adjacent characters for ( int color1 = 0; color1 < AlphabetSize; ++color1) { for ( int color2 = 0; color2 < AlphabetSize; ++color2) { if (!dp[i, color1, color2]) continue ; // Check conditions for assigning colors and update DP states if (currentChar >= color1) { dp[i + 1, currentChar, color2] = true ; parent[i + 1, currentChar, color2] = new Tuple<Tuple< int , int >, int >( new Tuple< int , int >(color1, color2), 0); } if (currentChar >= color2) { dp[i + 1, color1, currentChar] = true ; parent[i + 1, color1, currentChar] = new Tuple<Tuple< int , int >, int >( new Tuple< int , int >(color1, color2), 1); } } } } int lastColor1 = -1, lastColor2 = -1; // Find possible colors for the last character for ( int color1 = 0; color1 < AlphabetSize; ++color1) { for ( int color2 = 0; color2 < AlphabetSize; ++color2) { if (dp[n, color1, color2]) { lastColor1 = color1; lastColor2 = color2; } } } // If no valid colors found, print "NO" if (lastColor1 == -1) { Console.WriteLine( "NO" ); return ; } // Reconstruct the coloring string coloring = "" ; for ( int i = n; i > 0; --i) { int prevColor1 = parent[i, lastColor1, lastColor2].Item1.Item1; int prevColor2 = parent[i, lastColor1, lastColor2].Item1.Item2; if (parent[i, lastColor1, lastColor2].Item2 == 1) { coloring += '1' ; } else { coloring += '0' ; } lastColor1 = prevColor1; lastColor2 = prevColor2; } char [] reversedColoring = coloring.ToCharArray(); Array.Reverse(reversedColoring); coloring = new string (reversedColoring); // Print the result Console.WriteLine( "YES" ); Console.WriteLine(coloring); } } |
Javascript
const MaxLength = 222; const AlphabetSize = 26; const dp = new Array(MaxLength) .fill( false ) .map(() => new Array(AlphabetSize) .fill( false ) .map(() => new Array(AlphabetSize).fill( false )) ); const parent = new Array(MaxLength) .fill(0) .map(() => new Array(AlphabetSize).fill(0).map(() => new Array(AlphabetSize).fill(0))); function main() { const n = 9; const s = "abacbecfd" ; // Dynamic programming initialization dp[0][0][0] = true ; for (let i = 0; i < n; ++i) { const currentChar = s.charCodeAt(i) - 'a' .charCodeAt(0); // Iterate over possible colors for adjacent characters for (let color1 = 0; color1 < AlphabetSize; ++color1) { for (let color2 = 0; color2 < AlphabetSize; ++color2) { if (!dp[i][color1][color2]) continue ; // Check conditions for assigning colors // and update DP states if (currentChar >= color1) { dp[i + 1][currentChar][color2] = true ; parent[i + 1][currentChar][color2] = color1; } if (currentChar >= color2) { dp[i + 1][color1][currentChar] = true ; parent[i + 1][color1][currentChar] = color2 + AlphabetSize; } } } } let lastColor1 = -1, lastColor2 = -1; // Find possible colors for the last character for (let color1 = 0; color1 < AlphabetSize; ++color1) { for (let color2 = 0; color2 < AlphabetSize; ++color2) { if (dp[n][color1][color2]) { lastColor1 = color1; lastColor2 = color2; } } } // If no valid colors found, print "NO" if (lastColor1 === -1) { console.log( "NO" ); return ; } // Reconstruct the coloring let coloring = '' ; for (let i = n; i > 0; --i) { const prevColor = parent[i][lastColor1][lastColor2]; if (prevColor >= AlphabetSize) { coloring += '1' ; lastColor2 = prevColor - AlphabetSize; } else { coloring += '0' ; lastColor1 = prevColor; } } // Print the result console.log( "YES" ); console.log(coloring.split( '' ).reverse().join( '' )); } // Call the main function main(); |
YES 101100101
Time complexity: O(n * AL^2), where n is the length of the string and AL is the size of the Latin alphabet (26).
Auxiliary space: O(n * AL^2)
Contact Us