Given a binary string and k, to check whether it’s contains all permutations of length k or not.
Examples:
Input : Binary string 11001
k : 2
Output : Yes
11001 contains all possibilities of
binary sequences with k = 2, 00, 01,
10, 11
Input : Binary string: 1001
k : 2
Output: No
1001 does not contain all possibilities of
binary sequences with k = 2. Here 11
sequence is missing
Method 1:
Explanation: In this example one binary sequence of length k is not found it is 0110. So all binary sequences with k=4 will be 24=16. they are following 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 All should be sub string of given binary string then print Yes otherwise No
Algorithm:
Taking binary string and the size k. In binary string we check binary sequences are matched or not. Binary sequence is made of size k, as we know that in binary using 0 and 1 digit so to generate total binary subsets is 2k element. The main idea behind it, to store all binary value in list as string and then compare list all item to given binary string as subset. If all are occur inside the binary string then print “Yes” otherwise print “No”.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;// Generate all binary subsets of given length k.vector<string> binarySubsets(int k){ vector<string> list; // Loop for 2^k elements for (int i = 0; i < pow(2, k); i++) { // Add all possible binary sequence of given length // to the list list.push_back( bitset<32>(i).to_string().substr(32 - k)); } return list;}// Check if binary string contains all permutations of// length k.bool tocheck(const string& s, int k){ vector<string> list = binarySubsets(k); // Check if binary sequences are available in string or // not for (const auto& b : list) { if (s.find(b) == string::npos) { return false; } } return true;}// Driver codeint main(){ string str = "11001"; int num = 2; // Function call if (tocheck(str, num)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;}// This code is contributed by phasing17. |
Java
// Java program to Check a binary string// contains all permutations of length k.import java.util.*;public class Checkbinary { // to check all Permutation in given String public static boolean tocheck(String s, int k) { List<String> list = BinarySubsets(k); // to check binary sequences are available // in string or not for (String b : list) if (s.indexOf(b) == -1) return false; return true; } // to generate all binary subsets of given length k public static List<String> BinarySubsets(int k) { // Declare the list as String List<String> list = new ArrayList<>(); // to define the format of binary of // given length k String format = "%0" + k + "d"; // returns the string representation of the // unsigned integer value represented by // the argument in binary (base 2) using // Integer.toBinaryString and convert it // into integer using Integer.valueOf. // Loop for 2<sup>k</sup> elements for (int i = 0; i < Math.pow(2, k); i++) { // To add in the list all possible // binary sequence of given length list.add(String.format(format, Integer.valueOf(Integer.toBinaryString(i)))); /* To Show all binary sequence of given length k System.out.println(String.format(format, Integer.valueOf(Integer.toBinaryString(i))));*/ } return list; } // drive main public static void main(String[] args) { String str = "11001"; int num = 2; if (tocheck(str, num)) System.out.println("Yes"); else System.out.println("No"); }} |
Python3
# Python3 program to Check a binary string# contains all permutations of length k.def tocheck(s, k): list1 = binary_subsets(k) # to check binary sequences are available # in string or not for b in list1: if s.find(b) == -1: return False return True # to generate all binary subsets of given length kdef binary_subsets(k): # Declare the list as array list1 = [] # to define the format of binary of # given length k format = '0' * k # returns the string representation of the # unsigned integer value represented by # the argument in binary (base 2) # Loop for 2^k elements for i in range(2 ** k): # To add in the list all possible # binary sequence of given length list1.append(format[0:k - len(bin(i)[2:])] + bin(i)[2:]) return list1 # driver codestring = "11001"num = 2# function callif tocheck(string, num): print("Yes")else: print("No")# This code is contributed by phasing17 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { // to check all Permutation in given String public static bool ToCheck(string s, int k) { var list = BinarySubsets(k); // to check binary sequences are available // in string or not foreach(string b in list) if (s.IndexOf(b) == -1) return false; return true; } // to generate all binary subsets of given length k public static List<string> BinarySubsets(int k) { // Declare the list as String var list = new List<string>(); // to define the format of binary of // given length k var format = "{0:D" + k + "}"; // Loop for 2^k elements for (int i = 0; i < Math.Pow(2, k); i++) { // To add in the list all possible // binary sequence of given length list.Add(string.Format(format, Convert.ToString(i, 2))); /* To Show all binary sequence of given length k Console.WriteLine(string.Format(format, Convert.ToString(i, 2)));*/ } return list; } // drive main public static void Main(string[] args) { var str = "11001"; var num = 2; if (ToCheck(str, num)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program to Check a binary string// contains all permutations of length k.function tocheck(s, k) { let list = binarySubsets(k); // to check binary sequences are available // in string or not for (let b of list) { if (s.indexOf(b) === -1) { return false; } } return true;}// to generate all binary subsets of given length kfunction binarySubsets(k) { // Declare the list as array let list = []; // to define the format of binary of // given length k let format = '0'.repeat(k); // returns the string representation of the // unsigned integer value represented by // the argument in binary (base 2) using // parseInt(n,2) and convert it // into integer using toString(2). // Loop for 2^k elements for (let i = 0; i < Math.pow(2, k); i++) { // To add in the list all possible // binary sequence of given length list.push(i.toString(2).padStart(k, '0')); } return list;}// driver codelet str = "11001";let num = 2;// function callif (tocheck(str, num)) { console.log("Yes");} else { console.log("No");}// This code is contributed by phasing17 |
Output
Yes
Method 2:
Algorithm:
Taking binary string and the size k. In binary string we check binary sequences are matched or not. Binary sequence is made of size k, as we know that in binary using 0 and 1 digit so to generate total binary subsets is 2k element.
The main idea behind it, to store all the substring of size k of the given string to the set i.e. storing the distinct substring of size k. If the size of the set is equal to 2k then print “YES” otherwise print “NO”.
Implementation:
C++
// C++ Program to Check If a // String Contains All Binary// Codes of Size K#include <bits/stdc++.h>using namespace std;#define int long longbool hasAllcodes(string s, int k){ // Unordered map of type string unordered_set<string> us; for (int i = 0; i + k <= s.size(); i++) { us.insert(s.substr(i, k)); } return us.size() == 1 << k;}// Driver Codesigned main(){ string s = "00110110"; int k = 2; if (hasAllcodes) { cout << "YES\n"; } else { cout << "NO\n"; }} |
Java
// Java Program to Check If a // String Contains All Binary// Codes of Size Kimport java.io.*;import java.util.*;class GFG{ static boolean hasAllcodes(String s, int k) { // Unordered map of type string Set<String> us= new HashSet<String>(); for(int i = 0; i + k <= s.length(); i++) { us.add(s.substring(i, i + k)); } return (us.size() == (1 << k)); } // Driver code public static void main (String[] args) { String s = "00110110"; int k = 2; if(hasAllcodes(s, k)) { System.out.println("YES"); } else { System.out.println("NO"); } }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 Program to Check If a # String Contains All Binary# Codes of Size Kdef hasAllcodes(s, k) : # Unordered map of type string us = set() for i in range(len(s) + 1) : us.add(s[i : k]) return len(us) == 1 << k# Driver codes = "00110110"k = 2if (hasAllcodes) : print("YES")else : print("NO") # This code is contributed by divyeshrabadiya07 |
C#
// C# Program to Check If a // String Contains All Binary// Codes of Size Kusing System;using System.Collections.Generic;class GFG { static bool hasAllcodes(string s, int k) { // Unordered map of type string HashSet<string> us = new HashSet<string>(); for (int i = 0; i + k <= s.Length; i++) { us.Add(s.Substring(i, k)); } return us.Count == 1 << k; } // Driver code static void Main() { string s = "00110110"; int k = 2; if(hasAllcodes(s, k)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }}// This code is contributed by divyesh072019 |
Javascript
<script>// Javascript program to Check If a// String Contains All Binary// Codes of Size Kfunction hasAllcodes(s,k){ // Unordered map of type string let us = new Set(); for(let i = 0; i + k <= s.length; i++) { us.add(s.substring(i, i + k)); } return (us.size == (1 << k));}// Driver codelet s = "00110110";let k = 2; if (hasAllcodes(s, k)){ document.write("YES");}else{ document.write("NO");}// This code is contributed by ab2127</script> |
Output
YES
Time Complexity: O(n) we iterating over string from index 0 to n-k, so O(n) time complexity
Space Complexity: O(2k) as here, in the above solution we are creating an unordered set which stores the all possible binary substring of size k so space complexity will be 2k
Method : 3 (Two Pointer Based)
In this method, we will take a window of size k and move that window to the end, and mark all possible permutations in the visited array. then check if there is any value that is not marked as visited then return false, otherwise return true.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;bool hasAllCodes(string s, int k){ int n = s.size(); if (n < k) return false; int size = pow(2, k); vector<bool> visited(size, false); int i = 0; int j = 0; int val = 0; while (j < k - 1) { val = 2 * val + (s[j] - '0'); j++; } while (j < n) { val = 2 * val + (s[j] - '0'); visited[val] = true; if (s[i] == '1') val -= pow(2, k - 1); j++; i++; } for (int i = 0; i < size; i++) { if (!visited[i]) return false; } return true;}// Driver Codeint main(){ string s = "00110110"; int k = 2; if (hasAllCodes(s, k)) { cout << "YES\n"; } else { cout << "NO\n"; }} |
Java
// Java program to implement the approachimport java.util.*;class GFG { // Method to check if the string contnains // all the binary codes of size k static boolean hasAllCodes(String s, int k) { int n = s.length(); if (n < k) return false; int size = (int)Math.pow(2, k); // ArrayList that tracks if a certain code // has been found ArrayList<Boolean> visited = new ArrayList<Boolean>(); for (int i = 0; i < size; i++) visited.add(false); int i = 0; int j = 0; int val = 0; while (j < k - 1) { val = 2 * val + (s.charAt(j) - '0'); j++; } while (j < n) { val = 2 * val + (s.charAt(j) - '0'); visited.set(val, true); if (s.charAt(i) == '1') val -= (int)Math.pow(2, k - 1); j++; i++; } // Checking if all the codes have been found for (i = 0; i < size; i++) { if (!visited.get(i)) return false; } return true; } // Driver Code public static void main(String[] args) { String s = "00110110"; int k = 2; // Function call if (hasAllCodes(s, k)) { System.out.print("YES\n"); } else { System.out.print("NO\n"); } }}// This code is contributed by phasing17 |
Python3
# Python3 Program to Check If a String Contains All Binary Codes of Size Kdef hasAllcodes(s, k): n = s.len() size = pow(2, k) visited = [True for i in range(size)] i = 0 j = 0 val = 0 while(j < k-1): val = (2 * val) + (s[j] - '0') j += 1 while(j < size): val = (2 * val) + (s[j] - '0') visited[val] = True if(s[i] == '1'): val = val - pow(2,k-1) j += 1 i += 1 for i in range(size): if(visited[i] == False): return False return True # Driver codes = "00110110"k = 2if (hasAllcodes): print("YES")else: print("NO") # This code is contributed by Ajay Makvana |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG{ // Method to check if the string contnains // all the binary codes of size k static bool hasAllCodes(string s, int k) { int n = s.Length; if (n < k) return false; int size = (int)Math.Pow(2, k); bool[] visited=new bool[size]; int i = 0; // ArrayList that tracks if a certain code // has been found for(i=0; i<size; i++) visited[i] = false; i=0; int j = 0; int val = 0; while (j < k - 1) { val = 2 * val + ((int)s[j]-'0'); j++; } while (j < n) { int x= ((int)s[j]-'0'); val = 2 * val + x; visited[val] = true; if (s[i] == '1') val -= ((int)Math.Pow(2, k - 1)); j++; i++; } for (i = 0; i < size; i++) { if (!visited[i]) return false; } return true; } // Driver Code static void Main(string[] args) { string s = "00110110"; int k = 2; if (hasAllCodes(s, k)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
// JavaScript Program to Check If a String Contains All Binary Codes of Size Kfunction hasAllcodes(s, k){ var n = s.length; var size = Math.pow(2, k); var visited = new Array(size).fill(true); var i = 0; var j = 0; var val = 0; while (j < k-1) { val = (2 * val) + (s[j] - '0'); j += 1; } while (j < size) { val = (2 * val) + (s[j] - '0'); visited[val] = true; if(s[i] == '1') val = val - Math.pow(2, k - 1); j += 1; i += 1; } for (var i = 0; i < size; i++) { if(visited[i] == false) return false; } return true;}// Driver codevar s = "00110110";var k = 2;if (hasAllcodes) console.log("YES");else console.log("NO"); // This code is contributed by phasing17 |
Output
YES
Time Complexity : O(n)
Space Complexity: O(2k) as here, in the above solution we are creating a visited array of size pow(2,k) so we need that extra space
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
