2207. Maximize Number of Subsequences in a String

發表於 | 分類於

problem

solution

將pattern[0] 插入第一個pattern[1] 之前
或是
將pattern[1] 插入第一個pattern[0] 之前

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    bool isUnique(string str){
        int n = str.size();
        for(int i=0;i<n-1;++i){
            if(str[i]!=str[i+1]) return false;
        }
        return true;
    }
    long long countSubseq(string str, string pattern){
    
        long long count = 0;
        int i =0, n = str.size();
        if(str[0] == pattern[1]) str.insert(0,string(1, pattern[0]));
        else{
            while(i<n && str[i+1]!=pattern[1]) i++;
            str.insert(i, string(1,pattern[0]));
        }

        unordered_map<char,int> mp;
        for(char c:str) mp[c]++;
        for(int i=0;i<str.size() ; ++i){
            if(str[i] == pattern[0]) count+=mp[pattern[1]];
            else mp[pattern[1]]--;
        }
        return count;
    }
    long long countSubseqB(string str, string pattern){
        
        long long count = 0;
        int n = str.size(),  i = n-1;
        if(str[i] == pattern[0]) str.insert(i+1, string(1, pattern[1]));
        else{
            while(i>0 && str[i-1] !=pattern[0]) i--;
            str.insert(i+1, string(1, pattern[1]));
        }
        unordered_map<char,int> mp;
        for(char c:str) mp[c]++;
        for(int i=0;i<str.size() ; ++i){
            if(str[i] == pattern[0]) count+=mp[pattern[1]];
            else mp[pattern[1]]--;
        }
        return count;
    }
    long long maximumSubsequenceCount(string text, string pattern) {
        string str ;
        for(char c:text){
            if(c == pattern[0] || c==pattern[1]) str+=c;
        }
        // insert before  first pattern[1] 
        if(str.empty()) return 0;
        if(isUnique(str) ){
            if(pattern[0] != pattern[1]) return str.size();
            else{
                return (str.size()+1)*(str.size()-1+1)/2;
            }
        }
        return max(countSubseq(str, pattern), countSubseqB(str, pattern));
        
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)