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 pbool 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-stringsvoid 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 codeint main(){ string s = "abepztydba"; int K = 4; int p = 110; countSubStrings(s, K, p); return 0;} |
Java
// Java implementation of the approachclass 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 approachusing 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 pfunction 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-stringsfunction 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 codevar s = "abepztydba";var K = 4;var p = 110;countSubStrings(s, K, p);</script> |
Output
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)
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!
