Java Solution 10 ms, find periods


  • 0
    F
    public class Solution {
        
        public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
    
            StringBuilder sb = new StringBuilder();
            int[] set = new int[128];
            for(int i = 0; i < s2.length(); i++){
                set[s2.charAt(i)] = 1;
            }
            for(int i = 0; i < s1.length(); i++){
                if(set[s1.charAt(i)] != 0){
                    sb.append(s1.charAt(i));
                    set[s1.charAt(i)] = -1;
                }
            }
    
            for(int i = 'a'; i <= 'z'; i++) if(set[i] > 0) return 0;
    
            s1 = sb.toString();
            int i = 0, j = 0, m = 0, n = 0;
            //map holds pos in s2 to pos in s1 and corresponding states;
            Map<Integer, int[]> map = new HashMap<>();
            Map<Integer, Integer> whole = new HashMap<Integer, Integer>(){{put(0,0);}};
            while(true){
                if(s2.charAt(j) == s1.charAt(i)){
                    j = (j + 1) % s2.length();
                    if(j == 0){
                        n++;
                        if(map.containsKey(i)) break;
                        else map.put(i, new int[]{m,n});
                    }
                }
                i = (i + 1) % s1.length();
                if(i == 0){
                    whole.put(++m, n);
                }
            }
            // {i, 0, newm, newn} --> {i, 0, oldm, oldn};
            int dm = m - map.get(i)[0];
            int dn = n - map.get(i)[1];
            int m1 = (n1 - map.get(i)[0] - 1)/dm;
            int res = m1 * dn;
            int remain = n1 - m1 * dm;
            return (res + whole.get(remain))/n2;
        }
    }
    

Log in to reply
 

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