Given a string str and an integer N, the task is to find the number of possible sub-strings of length N.
Examples:
Input: str = “w3wiki”, n = 5
Output: 9
All possible sub-strings of length 5 are “Beginner”, “eeksf”, “eksfo”,
“ksfor”, “sforg”, “forge”, “orgee”, “rgeek” and “Beginner”.
Input: str = “jgec”, N = 2
Output: 3
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
The approach used in this code is to iterate over all possible starting positions of a substring of length N in the given string str, and count the number of valid substrings. We can check if a substring is valid by using the substr function to extract a substring of length N starting from the current position, and checking if its length is equal to N.
C++
#include <bits/stdc++.h>
using namespace std;
int count_substrings(string str, int n) {
int count = 0;
for ( int i = 0; i <= str.length() - n; i++) {
string substring = str.substr(i, n);
if (substring.length() == n) {
count++;
}
}
return count;
}
int main() {
string str = "w3wiki" ;
int n = 5;
cout << count_substrings(str, n) << endl;
return 0;
}
|
Java
public class CountSubstrings {
public static int countSubstrings(String str, int n) {
int count = 0 ;
for ( int i = 0 ; i <= str.length() - n; i++) {
String substring = str.substring(i, i + n);
if (substring.length() == n) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String str = "w3wiki" ;
int n = 5 ;
System.out.println(countSubstrings(str, n));
}
}
|
Python3
def count_substrings(string, n):
count = 0
for i in range ( len (string) - n + 1 ):
substring = string[i:i + n]
if len (substring) = = n:
count + = 1
return count
str = "w3wiki"
n = 5
print (count_substrings( str , n))
|
C#
using System;
class GFG
{
static int CountSubstrings( string str, int n)
{
int count = 0;
for ( int i = 0; i <= str.Length - n; i++)
{
string substring = str.Substring(i, n);
if (substring.Length == n)
{
count++;
}
}
return count;
}
static void Main()
{
string str = "w3wiki" ;
int n = 5;
Console.WriteLine(CountSubstrings(str, n));
}
}
|
Javascript
function count_substrings(str, n) {
let count = 0;
for (let i = 0; i <= str.length - n; i++) {
let substring = str.substr(i, n);
if (substring.length === n) {
count++;
}
}
return count;
}
let str = "w3wiki" ;
let n = 5;
console.log(count_substrings(str, n));
|
Time Complexity: O(M*N), where M is the length of the input string str, since we iterate over N possible starting positions and extract a substring of length N each time.
Auxiliary Space: O(1), no extra space is required.
Approach: The count of sub-strings of length n will always be len – n + 1 where len is the length of the given string. For example, if str = “w3wiki” and n = 5 then the count of sub-strings having length 5 will be “Beginner”, “eeksf”, “eksfo”, “ksfor”, “sforg”, “forge”, “orgee”, “rgeek” and “Beginner” which is len – n + 1 = 13 – 5 + 1 = 9.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int countSubStr(string str, int n)
{
int len = str.length();
return (len - n + 1);
}
int main()
{
string str = "w3wiki" ;
int n = 5;
cout << countSubStr(str, n);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int countSubStr(String str, int n)
{
int len = str.length();
return (len - n + 1 );
}
public static void main(String args[])
{
String str = "w3wiki" ;
int n = 5 ;
System.out.print(countSubStr(str, n));
}
}
|
Python3
def countSubStr(string, n) :
length = len (string);
return (length - n + 1 );
if __name__ = = "__main__" :
string = "w3wiki" ;
n = 5 ;
print (countSubStr(string, n));
|
C#
using System;
class GFG
{
static int countSubStr( string str, int n)
{
int len = str.Length;
return (len - n + 1);
}
public static void Main()
{
string str = "w3wiki" ;
int n = 5;
Console.WriteLine(countSubStr(str, n));
}
}
|
Javascript
<script>
function countSubStr(str, n) {
var len = str.length;
return len - n + 1;
}
var str = "w3wiki" ;
var n = 5;
document.write(countSubStr(str, n));
</script>
|
PHP
<?php
function countSubStr( $str , $n )
{
$len = strlen ( $str );
return ( $len - $n + 1);
}
$str = "w3wiki" ;
$n = 5;
echo (countSubStr( $str , $n ));
?>
|
Time Complexity: O(1), it is a constant.
Auxiliary Space: O(1), no extra space is required.