2014. Longest Subsequence Repeated k Times LeetCode Solution

In this guide, you will get 2014. Longest Subsequence Repeated k Times LeetCode Solution with the best time and space complexity. The solution to Longest Subsequence Repeated k Times problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest Subsequence Repeated k Times solution in C++
Longest Subsequence Repeated k Times solution in Java
Longest Subsequence Repeated k Times solution in Python
Additional Resources

2014. Longest Subsequence Repeated k Times LeetCode Solution image

Problem Statement of Longest Subsequence Repeated k Times

You are given a string s of length n, and an integer k. You are tasked to find the longest subsequence repeated k times in string s.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
A subsequence seq is repeated k times in the string s if seq * k is a subsequence of s, where seq * k represents a string constructed by concatenating seq k times.

For example, “bba” is repeated 2 times in the string “bababcba”, because the string “bbabba”, constructed by concatenating “bba” 2 times, is a subsequence of the string “bababcba”.

Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.

Example 1:

Input: s = “letsleetcode”, k = 2
Output: “let”
Explanation: There are two longest subsequences repeated 2 times: “let” and “ete”.
“let” is the lexicographically largest one.

Example 2:

Input: s = “bb”, k = 2
Output: “b”
Explanation: The longest subsequence repeated 2 times is “b”.

Example 3:

Input: s = “ab”, k = 2
Output: “”
Explanation: There is no subsequence repeated 2 times. Empty string is returned.

Constraints:

n == s.length
2 <= n, k <= 2000
2 <= n < k * 8
s consists of lowercase English letters.

Complexity Analysis

Time Complexity: O(n \cdot P(7, k))
Space Complexity: O(P(7, k))

2014. Longest Subsequence Repeated k Times LeetCode Solution in C++

class Solution {
 public:
  string longestSubsequenceRepeatedK(string s, int k) {
    string ans;
    vector<int> count(26);
    vector<char> possibleChars;
    // Stores subsequences, where the length grows by 1 each time.
    queue<string> q{{""}};

    for (const char c : s)
      ++count[c - 'a'];

    for (char c = 'a'; c <= 'z'; ++c)
      if (count[c - 'a'] >= k)
        possibleChars.push_back(c);

    while (!q.empty()) {
      const string currSubseq = q.front();
      q.pop();
      if (currSubseq.length() * k > s.length())
        return ans;
      for (const char c : possibleChars) {
        const string& newSubseq = currSubseq + c;
        if (isSubsequence(newSubseq, s, k)) {
          q.push(newSubseq);
          ans = newSubseq;
        }
      }
    }

    return ans;
  }

 private:
  bool isSubsequence(const string& subseq, string& s, int k) {
    int i = 0;  // subseq's index
    for (const char c : s)
      if (c == subseq[i])
        if (++i == subseq.length()) {
          if (--k == 0)
            return true;
          i = 0;
        }
    return false;
  }
};
/* code provided by PROGIEZ */

2014. Longest Subsequence Repeated k Times LeetCode Solution in Java

class Solution {
  public String longestSubsequenceRepeatedK(String s, int k) {
    String ans = "";
    int[] count = new int[26];
    List<Character> possibleChars = new ArrayList<>();
    // Stores subsequences, where the length grows by 1 each time.
    Queue<String> q = new ArrayDeque<>(List.of(""));

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    for (char c = 'a'; c <= 'z'; ++c)
      if (count[c - 'a'] >= k)
        possibleChars.add(c);

    while (!q.isEmpty()) {
      final String currSubseq = q.poll();
      if (currSubseq.length() * k > s.length())
        return ans;
      for (final char c : possibleChars) {
        final String newSubseq = currSubseq + c;
        if (isSubsequence(newSubseq, s, k)) {
          q.offer(newSubseq);
          ans = newSubseq;
        }
      }
    }

    return ans;
  }

  private boolean isSubsequence(final String subseq, final String s, int k) {
    int i = 0; // subseq's index
    for (final char c : s.toCharArray())
      if (c == subseq.charAt(i))
        if (++i == subseq.length()) {
          if (--k == 0)
            return true;
          i = 0;
        }
    return false;
  }
}
// code provided by PROGIEZ

2014. Longest Subsequence Repeated k Times LeetCode Solution in Python

class Solution:
  def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
    ans = ''
    count = [0] * 26
    possibleChars = []
    # Stores subsequences, where the length grows by 1 each time.
    q = collections.deque([''])

    for c in s:
      count[ord(c) - ord('a')] += 1

    for c in string.ascii_lowercase:
      if count[ord(c) - ord('a')] >= k:
        possibleChars.append(c)

    def isSubsequence(subseq: str, s: str, k: int) -> bool:
      i = 0  # subseq's index
      for c in s:
        if c == subseq[i]:
          i += 1
          if i == len(subseq):
            k -= 1
            if k == 0:
              return True
            i = 0
      return False

    while q:
      currSubseq = q.popleft()
      if len(currSubseq) * k > len(s):
        return ans
      for c in possibleChars:
        newSubseq = currSubseq + c
        if isSubsequence(newSubseq, s, k):
          q.append(newSubseq)
          ans = newSubseq

    return ans
 # code by PROGIEZ