2287. Rearrange Characters to Make Target String

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> vec(26,0);
        for(char c:s) vec[c-'a']++;
        int count = 0 ;
        for(int _ = 0; _ < s.size()/target.size() ; ++_){
            for(char a:target){
                if(vec[a-'a'] < 1) return count;
                vec[a-'a']--;
            }
            count++;
        }
        return count;
    }
};

analysis

  • target complexity O(nm)
  • space complexity O(1)