Sliding Window Technique - Part 2

-
Crossing the 650 problems solved milestone today (weekends in covid-filled era are great for practicing algorithms)




1461. Check If a String Contains All Binary Codes of Size K
Medium

Given a binary string s and an integer k.

Return True if any binary code of length k is a substring of s. Otherwise, return False.

 

Example 1:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.

Example 2:

Input: s = "00110", k = 2
Output: true

Example 3:

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.

Example 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

Input: s = "0000000001011100", k = 4
Output: false

 

Constraints:

  • 1 <= s.length <= 5 * 10^5
  • s consists of 0's and 1's only.
  • 1 <= k <= 20
Accepted
4,299
Submissions
12,166

At first it looks a little daunting - generate all the 2^k possibilities and look each one up on the string of len |s|? That would bring the total execution time to 2^k * |s|, which would be in the worst case 2^20 * 5 * 10^5, or this: 524,288,000,000. You don't want that.
Instead, use the Sliding Window technique as shown in a previous post: as you traverse the string, for each window of size k, take that sub-string and insert into a hash table. At the end, if the hash table contains 2^k entries, you should return true (false otherwise). Brings the complexity down to |s|, much more reasonable. Code is below, cheers, ACC.


public class Solution
{
    public bool HasAllCodes(string s, int k)
    {
        if (String.IsNullOrEmpty(s)) return false;

        Hashtable code = new Hashtable();
        int target = (int)Math.Pow(2, k);

        string c = "";
        for (int i = 0; i < s.Length; i++)
        {
            c += s[i].ToString();

            if (i >= k)
            {
                c = c.Substring(1);
            }

            if (c.Length == k)
            {
                if (!code.ContainsKey(c))
                {
                    code.Add(c, true);
                    if (code.Count == target) return true;
                }
            }
        }

        return code.Count == target;
    }
}

Comments

  1. Prithvi ShankarJune 1, 2020 at 3:57 PM

    Changing from Hashtable to HashSet and removing the if condition (if(!code.ContainsKey(c)) improved the runtime by 12% and reduced the memory consumption a little :)

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more