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 = “neveropen”, n = 5
Output: 9
All possible sub-strings of length 5 are “neveropen”, “eeksf”, “eksfo”,
“ksfor”, “sforg”, “forge”, “orgee”, “rgeek” and “neveropen”.
Input: str = “jgec”, N = 2
Output: 3
Method 1:Naive Approach
Approach:
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.
Implementation:
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 = "neveropen";
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 = "neveropen";
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 = "neveropen"
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 = "neveropen";
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 = "neveropen";
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.
Method 2:Efficient Approach
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 = “neveropen” and n = 5 then the count of sub-strings having length 5 will be “neveropen”, “eeksf”, “eksfo”, “ksfor”, “sforg”, “forge”, “orgee”, “rgeek” and “neveropen” 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 = "neveropen";
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 = "neveropen";
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 = "neveropen";
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 = "neveropen";
int n = 5;
Console.WriteLine(countSubStr(str, n));
}
}
|
Javascript
<script>
function countSubStr(str, n) {
var len = str.length;
return len - n + 1;
}
var str = "neveropen";
var n = 5;
document.write(countSubStr(str, n));
</script>
|
PHP
<?php
function countSubStr($str, $n)
{
$len = strlen($str);
return ($len - $n + 1);
}
$str = "neveropen";
$n = 5;
echo(countSubStr($str, $n));
?>
|
Time Complexity: O(1), it is a constant.
Auxiliary Space: O(1), no extra space is required.
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!
