Sub-strings having exactly k characters that have ASCII value greater than p
Given a string ‘str’, two integers ‘k’ and ‘p’. The task is to count all the sub-strings of ‘str’ having exactly ‘k’ characters that have ASCII values greater than ‘p’.
Examples:
Input: str = “abcd”, k=2, p=98
Output: 3
Only the characters ‘c’ and ‘d’ have ASCII values greater than 98,
And, the sub-strings containing them are “abcd”, “bcd” and “cd”.Input: str = “sabrcd”, k=5, p=80
Output: 2
Approach: We just need to iterate over all indices and take all possible length sub-strings and then just check whether the sub-string has exactly ‘k’ characters that have ASCII value greater than ‘p’.
Typecasting a character to int will give us it’s ASCII value i.e. int ascii = (int) char.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that checks if // the string contain exactly // K characters having ASCII // value greater than p bool isValidSubString(string r, int K, int p) { int c = 0; for ( int i = 0; i < r.length(); i++) { // if ASCII value is // greater than 'p' if (( int )r[i] > p) c++; } // if count of satisfying // characters is equal to 'K' // then return true if (c == K) return true ; // otherwise return false else return false ; } // function to count sub-strings void countSubStrings(string s, int K, int p) { // length of the string int l = s.length(); // count of sub-strings int count = 0; // 'i' is the starting // index for the sub-string for ( int i = 0; i < l; i++) { // 'j' is the no. of characters // to include in the sub-string for ( int j = K; (i + j) <= l; j++) { string r = s.substr(i, j); // check if the sub-string // satisfies the condition if (isValidSubString(r, K, p)) count++; } } cout << count << "\n" ; } // Driver code int main() { string s = "abepztydba" ; int K = 4; int p = 110; countSubStrings(s, K, p); return 0; } |
Java
// Java implementation of the approach class GFG { // Function that checks if // the String contain exactly // K characters having ASCII // value greater than p boolean isValidSubString(String r, int K, int p) { int c = 0 ; for ( int i = 0 ; i < r.length(); i++) { // if ASCII value is // greater than 'p' if (( int )r.charAt(i) > p) { c++; } } // if count of satisfying // characters is equal to 'K' // then return true if (c == K) { return true ; } // otherwise return false else { return false ; } } // function to count sub-Strings void countSubStrings(String s, int K, int p) { // length of the String int l = s.length(); // count of sub-Strings int count = 0 ; // 'i' is the starting // index for the sub-String for ( int i = 0 ; i < l; i++) { // 'j' is the no. of characters // to include in the sub-String for ( int j = K; (i + j) <= l; j++) { String r = s.substring(i, (i + j)); // check if the sub-String // satisfies the condition if (isValidSubString(r, K, p)) { count++; } } } System.out.println(count); } // Driver code public static void main(String args[]) { GFG g = new GFG(); String s = "abepztydba" ; int K = 4 ; int p = 110 ; g.countSubStrings(s, K, p); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function that checks if the string # contain exactly K characters having # ASCII value greater than p def isValidSubString(r, K, p): c = 0 for i in range ( 0 , len (r)): # if ASCII value is # greater than 'p' if ord (r[i]) > p: c + = 1 # if count of satisfying # characters is equal to 'K' # then return true if c = = K: return True # otherwise return false else : return False # function to count sub-strings def countSubStrings(s, K, p): # length of the string l = len (s) # count of sub-strings count = 0 # 'i' is the starting # index for the sub-string for i in range ( 0 , l): # 'j' is the no. of characters # to include in the sub-string for j in range (K, l - i + 1 ): r = s[i:i + j] # check if the sub-string # satisfies the condition if isValidSubString(r, K, p) = = True : count + = 1 print (count) # Driver code if __name__ = = "__main__" : s = "abepztydba" K, p = 4 , 110 countSubStrings(s, K, p) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System; class GFG { // Function that checks if // the String contain exactly // K characters having ASCII // value greater than p bool isValidSubString(String r, int K, int p) { int c = 0; for ( int i = 0; i < r.Length; i++) { // if ASCII value is // greater than 'p' if (( int )r[i] > p) { c++; } } // if count of satisfying // characters is equal to 'K' // then return true if (c == K) { return true ; } // otherwise return false else { return false ; } } // function to count sub-Strings void countSubStrings(String s, int K, int p) { // length of the String int l = s.Length; // count of sub-Strings int count = 0; // 'i' is the starting // index for the sub-String for ( int i = 0; i < l; i++) { // 'j' is the no. of characters // to include in the sub-String for ( int j = K; (i + j) <= l; j++) { String r = s.Substring(i, j); // check if the sub-String // satisfies the condition if (isValidSubString(r, K, p)) { count++; } } } Console.WriteLine(count); } // Driver code public static void Main(String[] args) { GFG g = new GFG(); String s = "abepztydba" ; int K = 4; int p = 110; g.countSubStrings(s, K, p); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // JavaScript implementation of the approach // Function that checks if // the string contain exactly // K characters having ASCII // value greater than p function isValidSubString(r, K, p) { var c = 0; for ( var i = 0; i < r.length; i++) { // if ASCII value is // greater than 'p' if (r.charCodeAt(i) > p) c++; } // if count of satisfying // characters is equal to 'K' // then return true if (c == K) return true ; // otherwise return false else return false ; } // function to count sub-strings function countSubStrings(s, K, p) { // length of the string var l = s.length; // count of sub-strings var count = 0; // 'i' is the starting // index for the sub-string for ( var i = 0; i < l; i++) { // 'j' is the no. of characters // to include in the sub-string for ( var j = K; (i + j) <= l; j++) { var r = s.substring(i, i+j); // check if the sub-string // satisfies the condition if (isValidSubString(r, K, p)) count++; } } document.write( count + "<br>" ); } // Driver code var s = "abepztydba" ; var K = 4; var p = 110; countSubStrings(s, K, p); </script> |
16
Complexity Analysis:
- Time Complexity: O(N3), as we are using nested loops to traverse N*N times and also using inbuilt substring function which will cost us O(N) time.
- Auxiliary Space: O(N)
Contact Us