An algorithm to recursively count the number of sub string present in the given string in javascript.
Example
Input: 'learnersbucket' 'e' Output: 3
Implementation to recursively count the number of sub string in the given string
- We will check if the length of the original string is less than
n1 == 0
or less than the substringn1 < n2
, we will return0
. - Then we will check if there is a sub string match the given sub string in the original string.
- If it is present then we will call the same function by removing the substring and increasing the count.
- Else we will call the recursively same function to find sub string from one letter after the current.
let countSubString = (str, subStr, n1 = str.length, n2 = subStr.length) => { //If the string is empty //Or less than substring if(n1 === 0 || n1 < n2){ return 0; } //Check if there is a subString in the original string if(str.substring(0, n2) === subStr){ //Remove the substring from the original string and call the function with increased count return countSubString(str.substring(n2), subStr) + 1; } //Call same function with one letter less than original string return countSubString(str.substring(1), subStr); }
Input: console.log(countSubString('learnersbucket', 'e')); Output: 3
Time complexity: O(n).
Space complexity: O(n) (Call stack).
Working of above function
countSubString(){ //3 return countSubString(){ //1st index //2 return countSubString(){ //5th index //1 return countSubString(){ // 12th index //0 if(n1 === 0 || n1 < n2){ return 0; } } + 1; } + 1; } + 1; }