The k-th Lexicographical String of All Happy Strings of Length n
Problem Statement
Ek “happy string” ek aisa string hai jo:
Sirf letters [‘a’, ‘b’, ‘c’] ke set se hi banta hai.
s[i] != s[i + 1] har ek value ke liye from 1 to – 1. (Yeh string 1-indexed hai.)
For example, yeh strings “abc”, “ac”, “b” aur “abcbabcbcb” sab happy strings hain, lekin strings “aa”, “baa” aur “ababbc” happy strings nahi hain.
Ab, do integers n aur k diye gaye hain, to humein list ka consider karna hai jismein sab happy strings of length n lexicographical order mein sorted hain.
Humein is list ka kth string return karna hai ya fir return karna hai empty string agar wahan pe k se kam happy strings of length n hain.
Examples:
Example 1:
Input: n = 1, k = 3
Output: “c”
Explanation: List [“a”, “b”, “c”] contains all happy strings of length 1. Tisra string hai “c”.
Example 2:
Input: n = 1, k = 4
Output: “”
Explanation: Sirf 3 happy strings hain length 1 ke.
Example 3:
Input: n = 3, k = 9
Output: “cab”
Explanation: Total 12 different happy strings of length 3 hain [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”]. Aapko 9th string milegi “cab”.
Constraints:
1 <= n <= 10
1 <= k <= 100
The k-th Lexicographical String of All Happy Strings of Length n
Yeh solution DFS (Depth-First Search) ka use karta hai taaki sab possible happy strings generate ki ja sake aur k-th smallest string return ki ja sake:
DFS Traversal: DFS use karke recursively sab combinations of happy strings explore karte hain.
Lexicographical Order: Search ko 'a', 'b', aur 'c' se start karte hain taaki order maintain ho.
String Construction: Search ke dauran consecutive same characters avoid kiye jaate hain.
Efficient Search Pruning: Valid strings ki counting har step pe powers of 2 ke use se ki jaati hai. Aur pruning karke unnecessary exploration avoid karte hain based on remaining k.
DFS over Backtracking: DFS ko backtracking ke upar prefer kiya jaata hai kyunki yeh unnecessary exploration eliminate karta hai by counting valid strings har level pe.
Time Complexity: O(3^n) — Without pruning, sab possible combinations generate kiye jaate hain. Matlab, har character ke liye 3 choices (a, b, c). Lekin pruning se effective search reduce ho jaata hai kyunki kuch paths reject kar diye jaate hain jo valid happy strings nahi ban sakte.
Space Complexity: O(n) — Yeh space mainly recursion stack aur prefix string ke kaaran use hoti hai. Recursion stack mein n levels hoti hain kyunki maximum n length ka string generate ho raha hai.
Solution
var getHappyString = function(n, k) {
let n2 = n; // n2 ko original n ke equal rakhte hain
function dfs(prefix, n, k) {
if (n === 0) return prefix; // Agar n 0 hai to prefix return karte hain (base case)
for (let c of ['a', 'b', 'c']) { // Loop karte hain 'a', 'b', aur 'c' ke characters pe
if (prefix.length > 0 && c === prefix[prefix.length - 1]) continue; // Agar consecutive same characters hain to skip karte hain
let cnt = 2 ** (n2 - prefix.length - 1); // Valid strings ka count calculate karte hain using powers of 2
if (cnt >= k) return dfs(prefix + c, n - 1, k); // Agar count k ke barabar ya zyada hai to recursive DFS call karte hain
else k -= cnt; // Agar count k se kam hai to k me se count subtract karte hain
}
return ""; // Agar koi valid string nahi milti to empty string return karte hain
}
return dfs("", n, k); // Initial call to dfs function with empty prefix
};
Yeh function aim karta hai ki k-th “happy string” generate kare jiska length n ho, using Depth-First Search (DFS).
Setup: Kuch variables initialize karte hain. Happy string ka length n2 ke naam se refer karte hain.
DFS Function: Ek recursive function hota hai jo yeh karta hai:
Base Case: Agar n 0 ho jaata hai, iska matlab required length ka string build ho gaya, toh yeh string return karte hain.
Loop Through ‘a’, ‘b’, ‘c’: Hum in characters ko ek-ek karke apne string mein add karne ki koshish karte hain.
Avoid Repeating Characters: Character add karne se pehle check karte hain ki yeh last waale character ke same toh nahi hai. Agar same ho, toh skip karte hain.
Count Valid Strings: Har character ke liye count karte hain kitne valid strings ban sakte hain, using powers of 2.
Pruning: Agar valid strings ka count k se zyada ya barabar hai, toh hum DFS call karte hain is character ke saath. Agar nahi, toh count ko k me se subtract kar dete hain.
Return Empty String: Agar koi valid string nahi milti, toh empty string return karte hain.
Return Result: Finally, DFS function ko initially ek empty string ke saath call karte hain aur result return karte hain.
Solution
class Solution {
int n2; // n2 ko original n ke equal rakhte hain
string dfs(string prefix, int n, int k) {
if (n == 0) // Base case: Agar n 0 ho gaya toh prefix return karte hain
return prefix;
for (char c = 'a'; c <= 'c'; c++) { // 'a', 'b', 'c' ke characters loop karte hain
if (!prefix.empty() && c == prefix.back()) // Agar consecutive same characters hain toh skip karte hain
continue;
int cnt = (1 << (n2 - prefix.length() - 1)); // Valid strings ka count calculate karte hain using powers of 2
if (cnt >= k) // Agar count k ke barabar ya zyada hai toh recursive DFS call karte hain
return dfs(prefix + c, n - 1, k);
else
k -= cnt; // Agar count k se kam hai toh k me se count subtract karte hain
}
return ""; // Agar koi valid string nahi milti toh empty string return karte hain
}
public:
string getHappyString(int n, int k) {
n2 = n; // n2 ko original n ke equal rakhte hain
return dfs("", n, k); // Initial call to DFS function with empty prefix
}
};
