A happy string is a string that:
consists only of letters of the set ['a', 'b', 'c'].
s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.
Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.Return the kth string of this list or return an empty string if there are less than k happy strings of length n.
Example 1:
Input: n = 1, k = 3
Output: “c”
Explanation: The list [“a”, “b”, “c”] contains all happy strings of length 1. The third string is “c”.
Flow Diagram: –
Solution :-
class Solution {
public String getHappyString(int n, int k) {
char[] arr = {'a', 'b', 'c'};
String res="";
List<String> l=new ArrayList<>();
generatePerm(arr, n, res, l);
if(l.size() >= k)
res=l.get(k-1);
return res;
}
private void generatePerm(char[] arr, int n, String res, List<String> l){
if(n == 0){
l.add(res);
return;
}
for(int i=0; i<arr.length; i++){
if(res == "" || res.charAt(res.length()-1) != arr[i]){
String pre=res+arr[i];
generatePerm(arr, n-1, pre, l);
}
}
}
}