Lexicographically smallest String using all of the first K letters of alphabet and no two adjacent characters are same
Given two integers N and K, the task is to form a string of size N using the first K characters of the alphabet following the given conditions:
- No two adjacent characters of the string are the same.
- All of the K characters are present at least once in the string.
If no such string is possible, print -1.
Examples:
Input: N = 3, K = 2
Output: “aba”
Explanation: This is the lexicographically smallest string which follows the condition.
“aaa” is lexicographically smallest string of size 3, but this does not contain ‘b’.
So it is not a valid string according to the statement.
“aab” is also lexicographically smaller, but it violates the condition of two adjacent characters not being the same.Input: N = 2, K = 3
Output: -1
Explanation: Have to choose first 3 characters, but a string of only 2 size should be formed.
So it is not possible to use all of the first 3 characters.
Approach: This is an implementation based problem. As known, if the starting characters of the alphabet are used at the starting of the string, then the string will be lexicographically smaller. Follow the steps mentioned below:
- if N < K or K = 1 and N > 1 then print ‘-1’ as forming a string that satisfies both the condition is not possible.
- Otherwise, if N = 2 then print “ab”.
- If N > 2 then add ‘a’ and ‘b’ in the resultant string alternatively until the remaining length is K-2. Then add the remaining characters except ‘a’ and ‘b’ in lexicographical order.
- The final string is the required string.
Below is the implementation of the above approach.
C++
// C++ program to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the // lexicographically smallest string string findmin( int N, int K) { // If size of given string is // more than first K letters of // alphabet then print -1. // If K = 1 and N > 1 then it // violates the rule that // adjacent characters should be different if (N < K or (K == 1 and N > 1)) return "-1" ; // If N = 2 then print "ab" if (N == 2) return "ab" ; string s; // Except "ab" add characters // in the string for ( int i = 2; i < K; i++) { s += char (i + 97); } string a = "ab" , b; int i = 0; while (i < N) { // Add 'a' and 'b' alternatively b += a[i % 2]; i++; // If there are other characters // than 'a' and 'b' if (N - i == K - 2) { for ( int i = 0; i < s.size(); i++) { b += s[i]; } break ; } } // Desired string return b; } // Driver code int main() { int N = 3, K = 2; // Function call cout << findmin(N, K); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the // lexicographically smallest string static String findmin( int N, int K) { // If size of given string is // more than first K letters of // alphabet then print -1. // If K = 1 and N > 1 then it // violates the rule that // adjacent characters should be different if (N < K || (K == 1 && N > 1 )) return "-1" ; // If N = 2 then print "ab" if (N == 2 ) return "ab" ; String s = "" ; // Except "ab" add characters // in the string for ( int i = 2 ; i < K; i++) { char ch = ( char )(i + 97 ); s += ch; } String a = "ab" , b = "" ; int i = 0 ; while (i < N) { // Add 'a' and 'b' alternatively b += a.charAt(i % 2 ); i++; // If there are other characters // than 'a' and 'b' if (N - i == K - 2 ) { for ( int j = 0 ; j < s.length();j++) { b += s.charAt(j); } break ; } } // Desired string return b; } // Driver code public static void main (String[] args) { int N = 3 , K = 2 ; System.out.println(findmin(N, K)); } } // This code is contributed by hrithikgarg03188. |
Python
# Python program to implement the approach # Function to find the # lexicographically smallest string def findmin(N, K): # If size of given string is # more than first K letters of # alphabet then print -1. # If K = 1 and N > 1 then it # violates the rule that # adjacent characters should be different if (N < K or (K = = 1 and N > 1 )): return "-1" # If N = 2 then print "ab" if (N = = 2 ): return "ab" s = "" # Except "ab" add characters # in the string for i in range ( 2 , K): s + = (i + 97 ) a = "ab" b = "" i = 0 while (i < N): # Add 'a' and 'b' alternatively b + = a[i % 2 ] i + = 1 # If there are other characters # than 'a' and 'b' if (N - i = = K - 2 ): for j in range ( len (s)): b + = s[i] break # Desired string return b # Driver code N = 3 K = 2 # Function call print (findmin(N, K)) # This code is contributed by Samim Hossain Mondal. |
C#
// C# program to implement the approach using System; class GFG { // Function to find the // lexicographically smallest string static string findmin( int N, int K) { // If size of given string is // more than first K letters of // alphabet then print -1. // If K = 1 and N > 1 then it // violates the rule that // adjacent characters should be different if (N < K || (K == 1 && N > 1)) return "-1" ; // If N = 2 then print "ab" if (N == 2) return "ab" ; string s = "" ; // Except "ab" add characters // in the string for ( int x = 2; x < K; x++) { s += ( char )(x + 97); } string a = "ab" , b = "" ; int i = 0; while (i < N) { // Add 'a' and 'b' alternatively b += a[i % 2]; i++; // If there are other characters // than 'a' and 'b' if (N - i == K - 2) { for ( int j = 0; j < s.Length; j++) { b += s[j]; } break ; } } // Desired string return b; } // Driver code public static void Main() { int N = 3, K = 2; // Function call Console.Write(findmin(N, K)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to implement the approach // Function to find the // lexicographically smallest string const findmin = (N, K) => { // If size of given string is // more than first K letters of // alphabet then print -1. // If K = 1 and N > 1 then it // violates the rule that // adjacent characters should be different if (N < K || (K == 1 && N > 1)) return "-1" ; // If N = 2 then print "ab" if (N == 2) return "ab" ; let s = "" ; // Except "ab" add characters // in the string for (let i = 2; i < K; i++) { s += String.fromCharCode(i + 97); } let a = "ab" , b = "" ; let i = 0; while (i < N) { // Add 'a' and 'b' alternatively b += a[i % 2]; i++; // If there are other characters // than 'a' and 'b' if (N - i == K - 2) { for (let i = 0; i < s.length; i++) { b += s[i]; } break ; } } // Desired string return b; } // Driver code let N = 3, K = 2; // Function call document.write(findmin(N, K)); // This code is contributed by rakeshsahni </script> |
aba
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us