C++ with string s1 pre-process, but got TLE


  • 0

    Re: [Ugly Java brute force solution](but accepted. 1088ms.)

    Similar to @shawngao 's Java brute force solution, I pre-processed string s1 to "cache" for each index j and char c, pre-calculate pos[j][c-'a'] as the index of first occurrence of char c stating from position j. This should help for two-pointer scanning, but I got TLE for test case with both s1, s2 as "aaaaaaaa..." and n1 = n2 = 1000000.

    After reading other posts, I see some coders also got TLE for C++ only (?). I am wondering whether my following C++ code indeed has defects.

        // pos[j][c]: index of first occurrence in string starting from index j for char c
        vector<vector<int>> pos;
        int getMaxRepetitions(string s1, int n1, string s2, int n2) {
          int counter = -1, ls1 = s1.size(), is = 0, cnt = 0; buildPos(s1, ls1); 
          while (++counter >= 0) {
              for (char c:s2) {
                if (is == ls1) { is = 0; if ((++cnt) >= n1) return counter/n2; }
                int next = pos[is][c-'a'];
                if (next == ls1) { 
                    if ((next = pos[0][c-'a']) == ls1) return counter/n2; 
                    if ((++cnt) >= n1) return counter/n2; 
                }
                is = next + 1;
              }
          }
          return -1; // should never comes here
        }
        // pre-process string s to find index of first occurrence starting from index j for char c
        void buildPos(string& s, int npos) {
          pos = vector<vector<int>>(s.size(), vector<int>(26, npos));
          vector<vector<int>> idx(26); int c;
          for (int i = 0; i < s.size(); ++i) {
            int last = idx[c = (s[i]-'a')].empty()? -1 : idx[c].back();
            idx[c].push_back(i);
            for (int j = last+1; j <= i; ++j) pos[j][c] = i;
          }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.