2014 longest subsequence repeated K times

Supplementary questions for game 259

2014. Longest subsequence repeated K times

Give you a string s of length n and an integer k. Please find the longest subsequence repeated k times in string s.

A subsequence is a string derived from other strings with some (or no) characters deleted.

If seq * k is a subsequence of S, where seq * k represents a string constructed by seq concatenation K times, then seq is said to be a subsequence repeated K times in string s.

  • For example, "bba" is a subsequence repeated twice in the string "bababcba", because the string "bbabba" is constructed by concatenating "bba" twice, and "bbabba" is a subsequence of the string "* * * b***a***bab***c***ba * * *".

Returns the longest subsequence repeated k times in the string s. If there are multiple satisfied subsequences, the one with the largest dictionary order is returned. If no such subsequence exists, an empty string is returned.

Example 1:

Input: s = "letsleetcode", k = 2
 Output:"let"
Explanation: there are two longest subsequences repeated twice: let" and "ete" . 
"let" It is the one with the largest dictionary order.

Example 2:

Input: s = "bb", k = 2
 Output:"b"
Explanation: the longest subsequence repeated twice is "b" . 

Example 3:

Input: s = "ab", k = 2
 Output:""
Explanation: there is no longest subsequence repeated twice. Returns an empty string.

Example 4:

Input: s = "bbabbabbbbabaababab", k = 3
 Output:"bbbb"
Explanation: in "bbabbabbbbabaababab" The longest subsequence repeated 3 times in is "bbbb" . 

Tips:

  • n == s.length
  • 2 <= k <= 2000
  • 2 <= n < k * 8
  • s consists of lowercase English letters
class Solution {
public:
    bool check(string str, string s, int k){
        int n = s.size(), m = str.size();
        int j = 0;
        for(int i = 0; i < k; ++ i){
            int l;
            for(l = 0; j < n && l < m; ++ j){
                if(s[j] == str[l]){
                    l ++;
                    s[j] = '#';
                }
            }
            if(l < m)return false;
        }
        return true;
    }

    string longestSubsequenceRepeatedK(string s, int k) {
        int n = s.size();
        vector<char> vc;
        vector<string> vs;
        map<char, int> mp;
        for(auto ch : s){
            mp[ch] ++;
        }
        for(auto m : mp){
            if(m.second >= k){
                vc.push_back(m.first);
                vs.push_back(string(1, m.first));
            }
        }
        while(true){
            vector<string> nvs;
            for(auto str : vs){
                for(auto ch : vc){
                    str.push_back(ch);
                    if(check(str, s, k) == true){
                        nvs.push_back(str);
                    }
                    str.erase(str.end() - 1);
                }
            }
            if(nvs.empty())break;
            vs = nvs;
        }
        string ans = "";
        for(int i = 0; i < vs.size(); ++ i){
            if(vs[i].size() == ans.size() && vs[i] > ans){
                ans = vs[i];
            }else if(vs[i].size() > ans.size()){
                ans = vs[i];
            }
        }
        return ans;
    }
};

Algorithm idea:

A very important hint of this question is 2 < = n < k * 8. If a character wants to appear in the result string, the number of times it appears must be greater than or equal to K, which means that the length of the answer will not exceed 7, which in disguise shows that the data scale is very small, and violent enumeration can be solved. The specific problem-solving process is as follows:

  • First count the number of occurrences of each character in the string and select the characters that may form the answer (the number of occurrences is greater than or equal to k)
  • Start with a string of length 1 and continue to add characters back. Because the string of one character must be the result, first store it in VS to represent the qualified string, and then continuously add a suffix to the string in vs. the suffix is selected from the characters whose occurrence times are greater than or equal to k. judge whether it meets the subject conditions. If it meets the conditions, fill in nvs, indicating that a longer string meets the conditions. After the traversal of VS is completed, if nvs is empty, it indicates that the longest string already exists in vs. if nvs is not empty, it indicates that there are still longer strings that meet the conditions. Vs is cleared, nvs is assigned to VS, and the traversal continues.
  • To judge whether the string meets the conditions, you only need to traverse s. note that several substrings do not intersect, so the O(n) complexity can be solved.

If nvs is empty, it indicates that the longest string already exists in vs. if nvs is not empty, it indicates that there are still longer strings that meet the conditions. Vs is cleared, nvs is assigned to VS, and continue traversal.

  • To judge whether the string meets the conditions, you only need to traverse s. note that several substrings do not intersect, so the O(n) complexity can be solved.

Tags: Algorithm data structure leetcode

Posted by jdorma0 on Tue, 21 Sep 2021 01:50:37 +0530