2014. Longest Subsequence Repeated k Times

Problem

Given a string s and an integer k, you need to find the longest subsequence in the string such that the subsequence is repeated k times. The characters in the subsequence are selected conservatively(function in program). If there are multiple such subsequences, you need to return the lexicographically largest one. If the answer is empty, return an empty string.

You can think of it as finding out the maximum-length string which could be a repeated subsequence.

Example

1
2
3Input: s = "abcacb", k = 2
4Output: "ab"
5Explanation: The longest subsequence that occurs at least 2 times is "ab".

Approach

The solution for this problem involves using a BFS (Breadth-First Search) algorithm, along with a queue-based data structure. The solution uses a function isSubsequence that returns true if the given subsequence is a subsequence of the string for k times and false otherwise. The algorithm first keeps track of the count of each character in the string, a possible character set, and initials an empty queue with an empty string. Then, it dequeues a subsequence from the queue, and if its length times k is greater than the length of the string, it returns the answer. Otherwise, it iterates over the possible characters, forms new subsequences, and adds them to the queue if they are subsequences of the string. Finally, the answer is returned.

Example

Using the input example s = "abcacb", k = 2, the algorithm works as follows:

1. Count each character's frequency in the string: a:2, b:2, c:2
2. Create a list of possible characters: ['a', 'b', 'c']
3. Initialize the queue with an empty string: [""]
4. Iterate through the BFS queue, forming new subsequences ("a", "ab", "ac", "abc", "acb", "b", "ba", "bc", "bc", "bca", "ca", "cac", "cab", "c", "c").
5. While iterating over the new subsequences, add them to the BFS queue if they're subsequences of the string. For example, "ab" is a subsequence of the string, so it's added to the queue: ["", "a", "ab", "ac", "abc", "acb", "b", "ba", "bc", "bc", "bca", "ca", "cac", "cab", "c", "c"].
6. Return the largest lexicographically-valid subsequence, which is "ab" in this example.

Algorithm Steps

1. Initialize a count array to store the frequency of each character in the string.
2. Initialize a possible Characters list that contains characters occurring k times in the string.
3. Initialize a BFS queue with an empty string.
4. While the queue is not empty:
   1. Dequeue one subsequence from the queue.
   2. If the length of the subsequence times k is greater than the length of the string, return the answer.
   3. Iterate through the possible characters list, form new subsequences, and add them to the queue if they're subsequences of the string.

Solution

Python

1
2python
3from collections import deque
4from typing import List
5
6class Solution:
7    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
8        def is_subsequence(subseq: str, s: str, k: int) -> bool:
9            i = 0
10            for c in s:
11                if c == subseq[i]:
12                    i += 1
13                    if i == len(subseq):
14                        k -= 1
15                        if k == 0:
16                            return True
17                        i = 0
18            return False
19
20        count = [0] * 26
21        possible_chars = []
22        bfs_queue = deque([""])
23
24        for c in s:
25            count[ord(c) - ord('a')] += 1
26
27        for c in range(26):
28            if count[c] >= k:
29                possible_chars.append(chr(ord('a') + c))
30
31        ans = ""
32        while bfs_queue:
33            curr_subseq = bfs_queue.popleft()
34            if len(curr_subseq) * k > len(s):
35                return ans
36            for c in possible_chars:
37                new_subseq = curr_subseq + c
38                if is_subsequence(new_subseq, s, k):
39                    bfs_queue.append(new_subseq)
40                    ans = new_subseq
41
42        return ans

Java

1
2java
3import java.util.*;
4
5class Solution {
6    public String longestSubsequenceRepeatedK(String s, int k) {
7        int[] count = new int[26];
8        List<Character> possibleChars = new ArrayList<>();
9        Queue<String> q = new LinkedList<>(Collections.singletonList(""));
10
11        for (char c : s.toCharArray()) {
12            count[c - 'a']++;
13        }
14
15        for (char c = 'a'; c <= 'z'; c++) {
16            if (count[c - 'a'] >= k) {
17                possibleChars.add(c);
18            }
19        }
20
21        String ans = "";
22        while (!q.isEmpty()) {
23            String currSubseq = q.poll();
24            if (currSubseq.length() * k > s.length()) {
25                return ans;
26            }
27            for (char c : possibleChars) {
28                String newSubseq = currSubseq + c;
29                if (isSubsequence(newSubseq, s, k)) {
30                    q.offer(newSubseq);
31                    ans = newSubseq;
32                }
33            }
34        }
35
36        return ans;
37    }
38
39    private boolean isSubsequence(String subseq, String s, int k) {
40        int i = 0;
41        for (char c : s.toCharArray()) {
42            if (c == subseq.charAt(i)) {
43                i++;
44                if (i == subseq.length()) {
45                    k--;
46                    if (k == 0) {
47                        return true;
48                    }
49                    i = 0;
50                }
51            }
52        }
53        return false;
54    }
55}

JavaScript

1
2javascript
3class Solution {
4  longestSubsequenceRepeatedK(s, k) {
5    const count = new Array(26).fill(0);
6    const possibleChars = [];
7    const q = [""];
8    let ans = "";
9
10    for (const c of s) {
11      count[c.charCodeAt(0) - "a".charCodeAt(0)]++;
12    }
13
14    for (let i = 0; i < 26; i++) {
15      if (count[i] >= k) {
16        possibleChars.push(String.fromCharCode("a".charCodeAt(0) + i));
17      }
18    }
19
20    while (q.length > 0) {
21      const currSubseq = q.shift();
22      if (currSubseq.length * k > s.length) {
23        return ans;
24      }
25      for (const c of possibleChars) {
26        const newSubseq = currSubseq + c;
27        if (this.isSubsequence(newSubseq, s, k)) {
28          q.push(newSubseq);
29          ans = newSubseq;
30        }
31      }
32    }
33
34    return ans;
35  }
36
37  isSubsequence(subseq, s, k) {
38    let i = 0;
39    for (const c of s) {
40      if (c === subseq[i]) {
41        i++;
42        if (i === subseq.length) {
43          k--;
44          if (k === 0) {
45            return true;
46          }
47          i = 0;
48        }
49      }
50    }
51    return false;
52  }
53}

C++

1
2cpp
3#include <iostream>
4#include <queue>
5#include <string>
6#include <vector>
7
8class Solution {
9 public:
10  std::string longestSubsequenceRepeatedK(const std::string& s, int k) {
11    std::string ans;
12    std::vector<int> count(26);
13    std::vector<char> possibleChars;
14    std::queue<std::string> q{{""}};
15
16    for (const char c : s)
17      ++count[c - 'a'];
18
19    for (char c = 'a'; c <= 'z'; ++c)
20      if (count[c - 'a'] >= k)
21        possibleChars.push_back(c);
22
23    while (!q.empty()) {
24      const std::string currSubseq = q.front();
25      q.pop();
26      if (currSubseq.length() * k > s.length())
27        return ans;
28      for (const char c : possibleChars) {
29        const std::string& newSubseq = currSubseq + c;
30        if (isSubsequence(newSubseq, s, k)) {
31          q.push(newSubseq);
32          ans = newSubseq;
33        }
34      }
35    }
36
37    return ans;
38  }
39
40 private:
41  bool isSubsequence(const std::string& subseq, const std::string& s, int k) {
42    int i = 0;
43    for (const char c : s)
44      if (c == subseq[i])
45        if (++i == subseq.length()) {
46          if (--k == 0)
47            return true;
48          i = 0;
49        }
50    return false;
51  }
52};

C#

1
2csharp
3using System;
4using System.Collections.Generic;
5
6public class Solution {
7    public string LongestSubsequenceRepeatedK(string s, int k) {
8        int[] count = new int[26];
9        List<char> possibleChars = new List<char>();
10        Queue<string> q = new Queue<string>();
11        q.Enqueue("");
12        string ans = "";
13
14        foreach (char c in s) {
15            count[c - 'a']++;
16        }
17
18        for (char c = 'a'; c <= 'z'; c++) {
19            if (count[c - 'a'] >= k) {
20                possibleChars.Add(c);
21            }
22        }
23
24        while (q.Count > 0) {
25            string currSubseq = q.Dequeue();
26            if (currSubseq.Length * k > s.Length) {
27                return ans;
28            }
29            foreach (char c in possibleChars) {
30                string newSubseq = currSubseq + c;
31                if (IsSubsequence(newSubseq, s, k)) {
32                    q.Enqueue(newSubseq);
33                    ans = newSubseq;
34                }
35            }
36        }
37
38        return ans;
39    }
40
41    private bool IsSubsequence(string subseq, string s, int k) {
42        int i = 0;
43        foreach (char c in s) {
44            if (c == subseq[i]) {
45                i++;
46                if (i == subseq.Length) {
47                    k--;
48                    if (k == 0) {
49                        return true;
50                    }
51                    i = 0;
52                }
53            }
54        }
55        return false;
56    }
57}

Conclusion

In this article, we have explored the problem of finding the longest repeated subsequence of a string with given k times. We have provided algorithm steps to solve the problem using a BFS approach and shared the full solution in Python, Java, JavaScript, C++, and C#.

Solution Implementation