Length after removing Invalid K-Length Substrings
Given a string ‘S‘ of length N which consists of both Uppercase and Lowercase English alphabets and a positive integer K (1 <= K <= N), the task is to return the length of the resultant String after deleting all the Invalid substrings which are of length K from the given String. A String Is known as an Invalid String if every letter in String is present in both uppercase and lowercase with equal frequency with the length K then String is known as Invalid String.
Note: After Deleting all the Invalid substrings in the given string if the resultant string still contains invalid substrings don’t do any modifications just return the length of the resultant string.
Examples:
Input: S = “abcdaADCf”, K = 2
Output: 7
Explaination:
- In the above example, there is only one invalid string of length 2 it is “aA”.
- Because among every substring of length K in the given original string “aA” is the only invalid substring we need to delete it.
- After removing it the resultant string is “abcdDCf”.
- Here in the above resultant string, there is an invalid string of length 2 it is “dD”, but no modification should be done to the resultant string.
- Hence “dD” should not be deleted and the length of the resultant String is 7.
Input: S = “xyzAdaD”, K = 4
Output: 3
Explanation: The Substring “AdaD” is the only Invalid Substring and after deleting the Invalid Substring the String becomes “xyz”. Hence The Length is 3.
Approach: To Solve The Problem we can use the concept of sliding window algorithm as follows:
By using Sliding Window we can calculate the total length of all invalid substrings in given string, by removing these length from original string length we can get our required answer.
Follow the steps to solve the problem:
- Initialize two HashMap for tracking the LOWER and UPPER letter Frequencies.
- Initialize a head pointer and a tail pointer for tracking the substrings of size K.
- Initialize a invalidSubstringLength variable for storing total length of all invalid substrings.
- Iterate given string over loop using head pointer and calculate frequencies in HashMap’s.
- Whenever we find a substring of length K is invalid then add length of substring (K) to the invalidSubstringLength and slide the Substring Window by updating the tail value to point the start of new substring.
- After the iteration is completed return original string length – invalidSubstringLength as answer.
Below is the code to implement the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; bool isUpperCase( char a) { if (a >= 'A' && a <= 'Z' ) return true ; return false ; } int LengthOfResultantString(string s, int k) { // Initializing hashmaps for // storing frequency unordered_map< char , int > upper, lower; // Initializing required variables int head = 0, tail = 0, invalidSubstringLength = 0, originalLength = s.size(); for (head = 0; head < originalLength; head++) { // Verifing wheather the character is // uppercase or lowercase and // tracking frequency if (isUpperCase(s[head])) { upper[( char )s[head] + 32]++; } else lower[s[head]]++; if ((head - tail + 1) == k) { // 1) If the substring is invalid // then adding the length of // substring to invalidSubstringLength // and updating the tail pointer then // clearing the data stored in hashmaps // 2) If the substring is valid then // reduce the frequency of first // character in the substring if (upper == lower) { invalidSubstringLength = invalidSubstringLength + k; tail = head + 1; upper.clear(); lower.clear(); } else if (isUpperCase(s[tail])) { upper[( char )s[tail] + 32]--; if (upper[( char )s[tail] + 32] == 0) { upper.erase(( char )s[tail] + 32); } tail++; } else { lower[s[tail]]--; if (lower[s[tail]] == 0) { lower.erase(s[tail]); } tail++; } } } return originalLength - invalidSubstringLength; } // Drivers code int main() { string S = "xyzAdaD"; int K = 4; // Printing the length of resultant string cout << LengthOfResultantString(S, K); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.HashMap; import java.util.Map; class GFG { public static boolean isUpperCase( char a) { if (a >= 'A' && a <= 'Z' ) return true ; return false ; } public static int LengthOfResultantString(String s, int k) { // initializing hashmaps for storing frequency Map<Character, Integer> upper = new HashMap<>(); Map<Character, Integer> lower = new HashMap<>(); // initializing required variables int head = 0 , tail = 0 , invalidSubstringLength = 0 , originalLength = s.length(); for (head = 0 ; head < originalLength; head++) { /* verifing whether the character is uppercase or lowercase and tracking frequency */ if (isUpperCase(s.charAt(head))) { upper.put( ( char )(s.charAt(head) + 32 ), upper.getOrDefault( ( char )(s.charAt(head) + 32 ), 0 ) + 1 ); } else { lower.put( s.charAt(head), lower.getOrDefault(s.charAt(head), 0 ) + 1 ); } /* 1 )if the substring is invalid then adding the length of substring to invalidSubstringLength and updating the tail pointer then clearing the data stored in hashmaps 2 ) if the substring is valid then reduce the frequency of first character in the substring */ if ((head - tail + 1 ) == k) { if (upper.equals(lower)) { invalidSubstringLength = invalidSubstringLength + k; tail = head + 1 ; upper.clear(); lower.clear(); } else if (isUpperCase(s.charAt(tail))) { upper.put( ( char )(s.charAt(tail) + 32 ), upper.get( ( char )(s.charAt(tail) + 32 )) - 1 ); if (upper.get( ( char )(s.charAt(tail) + 32 )) == 0 ) { upper.remove( ( char )(s.charAt(tail) + 32 )); } tail++; } else { lower.put(s.charAt(tail), lower.get(s.charAt(tail)) - 1 ); if (lower.get(s.charAt(tail)) == 0 ) { lower.remove(s.charAt(tail)); } tail++; } } } return originalLength - invalidSubstringLength; } public static void main(String[] args) { String s = "xyzAdaD"; int k = 4 ; // printing the length of resultant string System.out.println(LengthOfResultantString(s, k)); } } |
Python
# Python code for the above approach def LengthOfResultantString(s, k): # Initializing hashmaps for # storing frequency upper, lower = {}, {} # Initializing required variables head, tail, invalidSubstringLength, originalLength = 0 , 0 , 0 , len (s) for head in range ( 0 , originalLength): # Verifing wheather the character is # uppercase or lowercase and # tracking frequency if s[head].isupper(): upper[ chr ( ord (s[head]) + 32 ) ] = upper.get( chr ( ord (s[head]) + 32 ), 0 ) + 1 else : lower[s[head]] = lower.get(s[head], 0 ) + 1 if (head - tail + 1 ) = = k: # 1) If the substring is invalid # then adding the length of # substring to invalidSubstringLength # and updating the tail pointer then # clearing the data stored in hashmaps # 2) If the substring is valid then # reduce the frequency of first # character in the substring if upper = = lower: invalidSubstringLength = invalidSubstringLength + k tail = head + 1 upper.clear() lower.clear() elif s[tail].isupper(): upper[ chr ( ord (s[tail]) + 32 )] - = 1 if (upper[ chr ( ord (s[tail]) + 32 )] = = 0 ): del upper[ chr ( ord (s[tail] + 32 ))] tail + = 1 else : lower[s[tail]] - = 1 if lower[s[tail]] = = 0 : del lower[s[tail]] tail + = 1 return originalLength - invalidSubstringLength # Drivers code if __name__ = = "__main__" : S = "xyzAdaD" K = 4 # Printing the length of resultant string print (LengthOfResultantString(S, K)) # This code is contribued by ragul21 |
C#
// C# code for the above approach: using System; using System.Collections.Generic; class GFG { static bool IsUpperCase( char a) { if (a >= 'A' && a <= 'Z' ) return true ; return false ; } static int LengthOfResultantString( string s, int k) { // Initializing dictionaries for storing frequency Dictionary< char , int > upper = new Dictionary< char , int >(); Dictionary< char , int > lower = new Dictionary< char , int >(); // Initializing required variables int head = 0; int tail = 0; int invalidSubstringLength = 0; int originalLength = s.Length; for (head = 0; head < originalLength; head++) { // Verifying whether the character is // uppercase or lowercase and // tracking frequency if (IsUpperCase(s[head])) { char lowerChar = ( char )(s[head] + 32); if (!upper.ContainsKey(lowerChar)) { upper[lowerChar] = 1; } else { upper[lowerChar]++; } } else { if (!lower.ContainsKey(s[head])) { lower[s[head]] = 1; } else { lower[s[head]]++; } } if ((head - tail + 1) == k) { // 1) If the substring is invalid // then adding the length of // substring to invalidSubstringLength // and updating the tail pointer then // clearing the data stored in hashmaps // 2) If the substring is valid then // reduce the frequency of first // character in the substring if (DictionaryEquals(upper, lower)) { invalidSubstringLength = invalidSubstringLength + k; tail = head + 1; upper.Clear(); lower.Clear(); } else if (IsUpperCase(s[tail])) { char lowerChar = ( char )(s[tail] + 32); if (upper.ContainsKey(lowerChar)) { upper[lowerChar]--; if (upper[lowerChar] == 0) { upper.Remove(lowerChar); } } tail++; } else { if (lower.ContainsKey(s[tail])) { lower[s[tail]]--; if (lower[s[tail]] == 0) { lower.Remove(s[tail]); } } tail++; } } } return originalLength - invalidSubstringLength; } static bool DictionaryEquals(Dictionary< char , int > dict1, Dictionary< char , int > dict2) { if (dict1.Count != dict2.Count) { return false ; } foreach ( var kvp in dict1) { if (!dict2.TryGetValue(kvp.Key, out int value) || value != kvp.Value) { return false ; } } return true ; } // Driver code static void Main() { string S = "xyzAdaD" ; int K = 4; // Printing the length of resultant string Console.WriteLine(LengthOfResultantString(S, K)); } } |
Javascript
// JavaScript code for the above approach: function IsUpperCase(a) { return a >= 'A' && a <= 'Z' ; } function LengthOfResultantString(s, k) { // Initializing objects for storing frequency let upper = new Map(); let lower = new Map(); // Initializing required variables let head = 0; let tail = 0; let invalidSubstringLength = 0; const originalLength = s.length; for (head = 0; head < originalLength; head++) { // Verifying whether the character is // uppercase or lowercase and // tracking frequency if (IsUpperCase(s[head])) { let lowerChar = String.fromCharCode(s.charCodeAt(head) + 32); if (!upper.has(lowerChar)) { upper.set(lowerChar, 1); } else { upper.set(lowerChar, upper.get(lowerChar) + 1); } } else { if (!lower.has(s[head])) { lower.set(s[head], 1); } else { lower.set(s[head], lower.get(s[head]) + 1); } } if (head - tail + 1 === k) { // 1) If the substring is invalid, // then add the length of the // substring to invalidSubstringLength, // update the tail pointer, and clear // the data stored in objects. // 2) If the substring is valid, then // reduce the frequency of the first // character in the substring. let isInvalid = false ; if (upper.size === lower.size) { for (let [key, value] of upper) { if (!lower.has(key) || lower.get(key) !== value) { isInvalid = true ; break ; } } } else { isInvalid = true ; } if (!isInvalid) { invalidSubstringLength = invalidSubstringLength + k; tail = head + 1; upper.clear(); lower.clear(); } else { if (IsUpperCase(s[tail])) { let lowerChar = String.fromCharCode(s.charCodeAt(tail) + 32); if (upper.has(lowerChar)) { upper.set(lowerChar, upper.get(lowerChar) - 1); if (upper.get(lowerChar) === 0) { upper. delete (lowerChar); } } tail++; } else { if (lower.has(s[tail])) { lower.set(s[tail], lower.get(s[tail]) - 1); if (lower.get(s[tail]) === 0) { lower. delete (s[tail]); } } tail++; } } } } return originalLength - invalidSubstringLength; } function DictionaryEquals(dict1, dict2) { if (dict1.size !== dict2.size) { return false ; } for (let [key, value] of dict1) { if (!dict2.has(key) || dict2.get(key) !== value) { return false ; } } return true ; } // Driver code let S = "xyzAdaD" ; let K = 4; // Printing the length of the resultant string console.log(LengthOfResultantString(S, K)); |
3
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(N), where N is the length of the string.