We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. How Many Substrings?
  5. Discussions

How Many Substrings?

  • genewangtp
     + 1 comment

    Sliding window would not help, already saw the solution, maybe it's a math test, but unfortunately I'm not a genius, if you can refactor my code, please help me.. the code only pass some case.

    int counting(string s, int length){
    int re=0;
    unordered_map<string, bool>mp;
    for(int i=0;i<length;i++){
        for(int j=1;j<=length-i;j++){
            string sub = s.substr(i,j);
            if(!mp[sub]){
                mp[sub]=true;
                re++;
            }
        }
    }    
    
    return re;
}
vector<int> countSubstrings(string s, vector<vector<int>> queries) {
    
    int length=queries.size();
    vector<int> re;
    
    for(int i=0;i<length;i++){
        int left = queries[i][0];
        int right = (left > 0) ? queries[i][1] : queries[i][1]+1;
        int length = queries[i][1]-queries[i][0]+1;
        int count = counting(s.substr(left, right), length);
        re.push_back(count);
    }
    return re;
}