No internal loop, java solution


  • 0
    Y

    The idea is building Histogram using the counts of characters.
    First build Histogram for s1
    Second build Histogram using a window of s2 of the length of s1.
    Third slide the window, and update the difference between the two Histograms.

        public  boolean checkInclusion(String s1, String s2) {
            if (s1.length() > s2.length()) return false;
            char[] cs1 = s1.toCharArray();
            char[] cs2 = s2.toCharArray();
    
            int R = 26;
    
            // Histogram of s1 and s2
            int[] Height1 = new int[R], Height2 = new int[R];
            for (int i = 0; i < cs1.length; ++i) {
                ++Height1[cs1[i] - 'a'];
                ++Height2[cs2[i] - 'a'];
            }
    
            // difference between Histogram1 and Histogram2
            int diff = 0;
            for (int i = 0; i < Height1.length; ++i)   diff += Math.abs(Height1[i] - Height2[i]);
            
            // Histogram of s2
            int lo = 0;
            int hi = s1.length() - 1;
            // slide window of s2[lo:hi]
            while (hi < s2.length()) {
                // diff 0 means that the two Histograms are the same
                if (0 == diff)  return true;
    
                // reduce the height of Height2[loIndex]
                int loIndex = cs2[lo] - 'a';
                if (Height2[loIndex] > Height1[loIndex])   --diff; 
                else                                       ++diff;    
                --Height2[loIndex];
    
                ++hi;
                if (hi >= s2.length())  break;
    
                // increase the height of Height2[hiIndex]
                int hiIndex = cs2[hi] - 'a';
                if (Height2[hiIndex] >= Height1[hiIndex])    ++diff;   
                else                                         --diff;
                ++Height2[hiIndex];
                ++lo;
            }
    
            return false;
        }
    
    

Log in to reply
 

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