Dada una string ‘str’, dos enteros ‘k’ y ‘p’. La tarea es contar todas las substrings de ‘str’ que tienen exactamente ‘k’ caracteres que tienen un valor ASCII mayor que ‘p’.
Ejemplos:
Entrada: str = “abcd”, k=2, p=98
Salida: 3
Solo los caracteres ‘c’ y ‘d’ tienen valores ASCII superiores a 98,
y las substrings que los contienen son “abcd”, “bcd ” y “cd”.
Entrada: str = “sabrcd”, k=5, p=80
Salida: 2
Enfoque: solo necesitamos iterar sobre todos los índices y tomar todas las substrings de longitud posibles y luego verificar si la substring tiene exactamente caracteres ‘k’ que tienen un valor ASCII mayor que ‘p’.
Encasillar un carácter a int nos dará su valor ASCII, es decir, int ascii = (int) char.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
16
Complejidad de tiempo: O(N 3 ), ya que estamos usando bucles anidados para atravesar N*N veces y también usando la función de substring incorporada que nos costará O(N) tiempo.
Espacio Auxiliar: O(N)