C# easy understand solution


  • 0
    T

    Idea is find index (both in s1 and s2) which start repeating before index in s1 going to the end..

    such as, assume n1 ,n2 is very large, for s1 = "abca" , s2 = "ac"
    i = [0, 2, 3, 2(6), 3(7), 2(10)] --> 6 is the real index, 2 is 6 % 4 == 2;
    j = [0, 1, 0(2), 1(3), 0(4), 1(5) ] --> 2 is the real index, 0 is 2%2 == 0;

    so for index i , 2->6->10 is repeat, for index j, 1->3->5 is repeat follow i.

    so from i=6, every 2 step increase is repeat. so it can ease calculate instead of increase one by one

    public class Solution {
        public int GetMaxRepetitions(string s1, int n1, string s2, int n2) {
            int len1 = s1.Length;
            int len2 = s2.Length;
            var dp = new string[len1,len2];
            int i = 0;
            int j = 0;
            bool find = false; 
            while(i/len1 < n1){
                if(s1[i%len1] == s2[j%len2]){
                    if(!find){
                        if(dp[i%len1,j%len2] == null){
                            dp[i%len1,j%len2] = i+","+j;
                        }else{
                            find = true;
                            var arr = dp[i%len1,j%len2].Split(new char[]{','});
                            
                            int ii = int.Parse(arr[0]);
                            int jj = int.Parse(arr[1]);
                            //Console.WriteLine(ii+","+jj+","+i+","+j);
                            int max = len1*n1;
                            int k = (max-i)/(i-ii);
                            //Console.WriteLine(k);
                            j = k*(j-jj)+j;
                            i = k*(i-ii)+i;
                        }
                    }
                    //Console.WriteLine(i+","+j);
                    i++;
                    j++;
                }else{
                    i++;
                }
            }
            
            return j/(len2*n2) -(len2*n2 == 1 ? 1 : 0);
            
        }
    }
    

Log in to reply
 

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