Package g1401_1500.s1415_the_k_th_lexicographical_string_of_all_happy_strings_of_length_n

Class Solution

java.lang.Object
g1401_1500.s1415_the_k_th_lexicographical_string_of_all_happy_strings_of_length_n.Solution
public class Solution extends Object
1415 - The k-th Lexicographical String of All Happy Strings of Length n.<p>Medium</p> <p>A <strong>happy string</strong> is a string that:</p> <ul> <li>consists only of letters of the set <code>['a', 'b', 'c']</code>.</li> <li><code>s[i] != s[i + 1]</code> for all values of <code>i</code> from <code>1</code> to <code>s.length - 1</code> (string is 1-indexed).</li> </ul> <p>For example, strings <strong>&ldquo;abc&rdquo;, &ldquo;ac&rdquo;, &ldquo;b&rdquo;</strong> and <strong>&ldquo;abcbabcbcb&rdquo;</strong> are all happy strings and strings <strong>&ldquo;aa&rdquo;, &ldquo;baa&rdquo;</strong> and <strong>&ldquo;ababbc&rdquo;</strong> are not happy strings.</p> <p>Given two integers <code>n</code> and <code>k</code>, consider a list of all happy strings of length <code>n</code> sorted in lexicographical order.</p> <p>Return <em>the kth string</em> of this list or return an <strong>empty string</strong> if there are less than <code>k</code> happy strings of length <code>n</code>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> n = 1, k = 3</p> <p><strong>Output:</strong> &ldquo;c&rdquo;</p> <p><strong>Explanation:</strong> The list [&ldquo;a&rdquo;, &ldquo;b&rdquo;, &ldquo;c&rdquo;] contains all happy strings of length 1. The third string is &ldquo;c&rdquo;.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> n = 1, k = 4</p> <p><strong>Output:</strong> &quot;&quot;</p> <p><strong>Explanation:</strong> There are only 3 happy strings of length 1.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> n = 3, k = 9</p> <p><strong>Output:</strong> &ldquo;cab&rdquo;</p> <p><strong>Explanation:</strong> There are 12 different happy string of length 3 [&ldquo;aba&rdquo;, &ldquo;abc&rdquo;, &ldquo;aca&rdquo;, &ldquo;acb&rdquo;, &ldquo;bab&rdquo;, &ldquo;bac&rdquo;, &ldquo;bca&rdquo;, &ldquo;bcb&rdquo;, &ldquo;cab&rdquo;, &ldquo;cac&rdquo;, &ldquo;cba&rdquo;, &ldquo;cbc&rdquo;]. You will find the 9<sup>th</sup> string = &ldquo;cab&rdquo;</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= n <= 10</code></li> <li><code>1 <= k <= 100</code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • getHappyString

      public String getHappyString(int n, int k)