Check valid substring of at least k length using Bit masking
Use Bitmasking to encode visited characters from index 0 to i and increment the count if the same mask occurred before.
Step-by-step approach:
- Create a map dp to store the first occurance of any mask of substring.
- Initialize dp[0] = -1, for one possible valid substring (if we don’t consider any character from the string).
- Iterate through the string from i = 0 to N-1.
- Calculate the current mask for the current character at the (S[i] – ‘a’) index.
- Check if same current mask exist in dp.
- If true then find the current substring length by (i – dp[current mask), if it is greater than or equal to k, return true
-
- Update the current mask with current index i in dp.
- Finally, return false.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to count all the valid substring long long allvalidString(string& word, int k) { // <current mask, first index for // this current mask> unordered_map< long long , long long > dp; long long mask = 0, result = 0; // One possible way for empty // mask at index -1 dp[0] = -1; for ( int i = 0; i < word.size(); i++) { char ch = word[i]; // Toggle the bit of mask at // (ch - 'a') index. mask ^= 1 << (ch - 'a' ); // If same mask exist previously if (dp.find(mask) != dp.end()) { // Check if current substring // is of size >= k if (i - dp[mask] >= k) return true ; } else { // Store the current index of // current mask into dp dp[mask] = i; } } // Return false return false ; } // Driver code int main() { string s = "bba"; int k = 2; // Function call cout << (allvalidString(s, k) ? " true " : " false "); return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { public static boolean allValidString(String word, int k) { Map<Long, Long> dp = new HashMap<>(); long mask = 0 ; long result = 0 ; dp.put(0L, -1L); for ( int i = 0 ; i < word.length(); i++) { char ch = word.charAt(i); mask ^= 1L << (ch - 'a' ); if (dp.containsKey(mask)) { if (i - dp.get(mask) >= k) { return true ; } } else { dp.put(mask, ( long )i); } } return false ; } public static void main(String[] args) { String s = "bba" ; int k = 2 ; // Function call System.out.println(allValidString(s, k) ? "true" : "false" ); } } |
Python
# Python code for the above approach # Function to count all the valid substring def all_valid_strings(word, k): # <current mask, first index for # this current mask> dp = {} mask = 0 result = 0 # One possible way for empty # mask at index -1 dp[ 0 ] = - 1 for i in range ( len (word)): ch = word[i] # Toggle the bit of mask at # (ord(ch) - ord('a')) index. mask ^ = 1 << ( ord (ch) - ord ( 'a' )) # If the same mask exists previously if mask in dp: # Check if the current substring # is of size >= k if i - dp[mask] > = k: return True else : # Store the current index of # the current mask into dp dp[mask] = i # Return False return False # Driver code s = "bba" k = 2 # Function call print ( "true" if all_valid_strings(s, k) else "false" ) # This code is contributed by Abhinav Mahajan (abhinav_m22) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { // Function to count all the valid substring public static bool AllValidString( string word, int k) { Dictionary< long , long > dp = new Dictionary< long , long >(); long mask = 0; dp[0L] = -1L; for ( int i = 0; i < word.Length; i++) { char ch = word[i]; mask ^= 1L << (ch - 'a' ); if (dp.ContainsKey(mask)) { if (i - dp[mask] >= k) { return true ; } } else { dp[mask] = i; } } return false ; } // Driver code public static void Main( string [] args) { string s = "bba" ; int k = 2; // Function call Console.WriteLine(AllValidString(s, k) ? "true" : "false" ); } } |
Javascript
function allvalidString(word, k) { // Create a Map to store the current mask and its first index const dp = new Map(); let mask = 0; let result = 0; // Initialize the Map with an empty mask at index -1 dp.set(0, -1); for (let i = 0; i < word.length; i++) { const ch = word[i].charCodeAt(0); // Toggle the bit of the mask at (ch - 'a') index mask ^= 1 << (ch - 'a' ); // If the same mask exists previously if (dp.has(mask)) { // Check if the current substring is of size >= k if (i - dp.get(mask) >= k) { return true ; } } else { // Store the current index of the current mask in the Map dp.set(mask, i); } } // Return false if no valid substring of size >= k is found return false ; } // Driver code const s = "bba" ; const k = 2; // Function call console.log(allvalidString(s, k) ? "true" : "false" ); |
Output
true
Time Complexity: O(N), where n is the length of the given string
Auxiliary Space: O(N)
Check valid Substring of at least k length
Given a string s (‘a’ <= s[i] <= ‘z’) and an integer k (1 <= k < n <= 105), the task is to check if any valid substrings of at least k length exist in the given string. A substring is valid if the occurrences of each character in the substring should be even.
Examples:
Input: s = “bba”, k = 2
Output: true
Explanation: Below is valid substring: “bba” -> “bb”Input: s = “aba”, k = 2
Output: false