Skip to content

2014. Longest Subsequence Repeated k Times 👍

  • Time: $O(n \cdot P(7, k))$
  • Space: $O(P(7, k))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public 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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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[string.ascii_lowercase.index(c)] += 1

    for c in string.ascii_lowercase:
      if count[string.ascii_lowercase.index(c)] >= 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