2140. Longest Subsequence Repeated K Times¶

Difficulty: Hard

2140. Longest Subsequence Repeated k Times

Hard

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:

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.

Solution¶

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public String longestSubsequenceRepeatedK(String s, int k) {
        int n = s.length();
        int freq[] = new int[26];
        for (int i = 0; i < n; i++)
            freq[s.charAt(i) - 'a']++;

        ArrayList<Character> validCharacters = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if (freq[i] >= k)
                validCharacters.add((char)(i + 'a'));
        }

        String ans = "";
        Queue<String> q = new LinkedList<>();
        q.offer("");
        while (q.size() > 0) {
            String curr = q.poll();
            for (char c : validCharacters) {
                String child = curr + c;
                if (isValid(s, child, k)) {
                    ans = child;
                    q.offer(child);
                }
            }
        }
        return ans;
    }
    private boolean isValid(String s, String temp, int k) {
        int n = s.length();
        String t = "";
        for (int i = 0; i < k; i++)
            t += temp;
        int m = t.length();

        if (m > n)
            return false;

        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else
                i++;
        }
        return j == m;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here