fast c++ beats 95%, variation of LeetCode 466 Count The Repetitions


  • 1
    G

    I found that this problem is basically LeetCode 466 Count the repetitions, with some variations.

    LeetCode 466 Count The Repetitions
    Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc".

    On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.

    You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

    Example:

    Input:
    s1="acb", n1=4
    s2="ab", n2=2

    Return:
    2

    For this problem, n1 is the col number, and n2 is the sentence length. s1 is an empty row with capacity of cols, s2 is the sentence.
    In stead of finding the how many substring s2 in s1, We find how many sentences we can fit in the empty row.

    I found @zhiqing_xiao 's explanation for 466 is very clear.
    C++ 0ms O(str1.length*str2.length):
    Here is the code with some minor modifications of @zhiqing_xiao 's answer to 466,

    class Solution {
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            // Let (pass2, idx2) denote that we cover a sentence for pass2 times,
           // and reach idx2-th word,
           // (pass2s, idx2s) stores the that, for pass1-th pass of a row,
    	// we cover a sentence for pass2s[pass1] times,
    	// and reach idx2s[pass1]-th word.
            int n = sentence.size();
            vector<int> pass2s(n + 1, -1);
            vector<int> idx2s(n + 1, -1);
            pass2s[0] = idx2s[0] = 0;
           // at the beginning, we are at (0, 0)
          // we will let all elements in idx2s be different
    	// according to pigeonhole principle,
    	// we only need sentence.size()+1 to find two elements 
    	// that are identical to each other.
    
            int pass2 = 0, idx2 = 0;
            for(int pass1 = 1; pass1 <= rows; ++ pass1){
               // Due to pigeonhole principle
    	   // we are sure to break within O(sentence.size()) iterations
                int len = 0, cnt = 0, idx1 = 0;
                while(len + sentence[idx2].size() <= cols - cnt){
                    len += sentence[idx2].size();
                    cnt ++;
                    idx2 ++;
                    if(idx2 == n){
                        idx2 = 0; pass2 ++;
                    }
                }
                pass2s[pass1] = pass2;
                idx2s[pass1] = idx2;
               // try to find the repetitive part
                for(int prevPass1 = 0; prevPass1 < pass1; ++prevPass1){
                    if(idx2s[prevPass1] == idx2){
                        int repeatCount = (rows - prevPass1) / (pass1 - prevPass1);
                        int remainPass1Count = (rows - prevPass1) % (pass1 - prevPass1);
                        int prefixPass2Num = pass2s[prevPass1];
                        int repetivePass2Num = repeatCount * (pass2s[pass1] - pass2s[prevPass1]);
                        int suffixPass2Num = pass2s[prevPass1 + remainPass1Count] - pass2s[prevPass1];
                        int overallPass2Num = prefixPass2Num + repetivePass2Num + suffixPass2Num;
                        return overallPass2Num;
                    }
                }
            }
            return pass2s[rows];
        }
    };
    

Log in to reply
 

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