Count occurrences of a sub-string with one variable character
Given two strings a and b, and an integer k which is the index in b at which the character can be changed to any other character, the task is to check if b is a sub-string in a and print out how many times b occurs in a in total after replacing the b[k] with every possible lowercase character of English alphabet.
Examples:
Input: a = “Beginner”, b = “ee”, k = 1
Output: 1 Replace b[1] with ‘k’ and “ek” is a sub-string in “Beginner” “ee” is also a sub-string in “Beginner” Hence the total count is 2
Input: a = “dogdog”, b = “dop”, k = 2
Output: 2 Replace b[2] with ‘g’, “dog” is a sub-string in “dogdog” which appears twice.
Approach: Make a list of all possible versions of the string b by iterating through all the lowercase letters and replacing the kth i.e. b[k] character in b with the current character. Then count the number of occurrence of the new string b in the original string a and store it in a variable count. After all the lowercase characters are used, print the count.
Below is the implementation of the above approach:
C++
// c++ implementation of above approach #include <bits/stdc++.h> using namespace std; // function to implement count int count_(string a, string var) { int c = 0; int l = var.length(); for ( int i = 0; i < a.length() - l; i++) if (a.substr(i, l) == var) c++; return c; } // Function to return the count of occurrences int countOccurrence(string a, string b, int k) { // Generate all possible substrings to // be searched vector<string> x; for ( int i = 0; i < 26; i++) { string temp = b; temp[k] = 'a' + i; x.push_back(temp); } // Now search every substring 'a' and // increment count int count = 0; for ( auto var : x) { if (a.find(var) != string::npos) count += count_(a, var); } return count; } int main() { string a = "Beginner" , b = "ee" ; int k = 1; cout << countOccurrence(a, b, k) << endl; return 0; } // This code is contributed by Abhijeet Kumar(abhijeet19403) |
Java
// Java program for the above approach import java.util.*; public class Main { // function to implement count public static int count_(String a, String var) { int c = 0 ; int l = var.length(); for ( int i = 0 ; i < a.length() - l; i++) { if (a.substring(i, i + l).equals(var)) { c++; } } return c; } // Function to return the count of occurrences public static int countOccurrence(String a, String b, int k) { // Generate all possible substrings to be searched List<String> x = new ArrayList<>(); for ( int i = 0 ; i < 26 ; i++) { char [] temp = b.toCharArray(); temp[k] = ( char )( 'a' + i); x.add(String.valueOf(temp)); } // Now search every substring 'a' and increment count int count = 0 ; for (String var : x) { if (a.indexOf(var) != - 1 ) { count += count_(a, var); } } return count; } public static void main(String[] args) { String a = "Beginner" ; String b = "ee" ; int k = 1 ; System.out.println(countOccurrence(a, b, k)); } } // This code is contributed by Prince Kumar |
Python3
# Python3 implementation of the approach import string # Function to return the count of occurrences def countOccurrence(a, b, k): # Generate all possible substrings to # be searched x = [] for i in range ( 26 ): x.append(b[ 0 :k] + string.ascii_lowercase[i] + b[k + 1 :]) # Now search every substring 'a' and # increment count count = 0 for var in x: if var in a: count + = a.count(var) return count # Driver code a, b = "Beginner" , "ee" k = 1 print (countOccurrence(a, b, k)) |
Javascript
// JavaScript implementation of the approach // Function to return the count of occurrences function countOccurrence(a, b, k) { let x = []; // Generate all possible substrings to be searched for (let i = 0; i < 26; i++) { x.push(b.substring(0, k) + String.fromCharCode(97 + i) + b.substring(k + 1)); } // Now search every substring 'a' and increment count let count = 0; for (let var1 of x) { if (a.includes(var1)) { count += a.split(var1).length - 1; } } return count; } // Driver code let a = "Beginner" ; let b = "ee" ; let k = 1; console.log(countOccurrence(a, b, k)); |
C#
// c# implementation of above approach using System; using System.Collections.Generic; class GFG { // function to implement count static int count_( string a, string var ) { int c = 0; int l = var .Length; for ( int i = 0; i < a.Length - l; i++) if (a.Substring(i, l) == var ) c++; return c; } // Function to return the count of occurrences static int countOccurrence( string a, string b, int k) { // Generate all possible substrings to // be searched List< string > x = new List< string >(); for ( int i = 0; i < 26; i++) { string temp = b; temp = temp.Remove(k, 1).Insert( k, Convert.ToString(( char )( 'a' + i))); x.Add(temp); } // Now search every substring 'a' and // increment count int count = 0; foreach ( var var in x) { if (a.Contains( var )) count += count_(a, var ); } return count; } static void Main() { string a = "Beginner" , b = "ee" ; int k = 1; Console.WriteLine(countOccurrence(a, b, k)); } } |
2