Given a string str, the task is to find the number of distinct substrings that are placed consecutively in the given string.
Examples:
Input: str = “neveropenneveropen”
Output: 2
Explanation:
neveropenneveropenforneveropen -> {“neveropen”}
geeksgeeksforgeeks -> {“e”}
Only one consecutive occurrence of “e” is considered.
Therefore two distinct substrings {“neveropen”, “e”} occur consecutively in the string.
Therefore, the answer is 2.Input: s = “neveropen”
Output: 1
Explanation:
geeksneveropen -> {“e”, “e”}
Only one substring {“e”} occurs consecutively in the string.
Naive Approach:
The simplest approach is to generate all possible substrings of the given string, and for each substring, find the count of substrings in the given occurring consecutively in the string. Finally, print the count.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach:
To optimize the above approach, the idea is to use Dynamic Programming.
Follow the steps below to solve the problem:
- If the length of the string does not exceed 1, then it is not possible to find any such consecutively placed similar substrings. So return 0 as the count.
- Otherwise, initialize a memoization table dp[] of dimensions (N+1 * N+1) which is initialized to 0.
- Initialize an unordered_set to store the distinct substrings placed consecutively.
- Iterate from the end of the string.
- While traversing the string if any repeating character is found, then dp[i][j] will be determined considering the previously computed dp value i.e., count of identical substrings up to dp[i+1][j+1] characters and including the current character.
- If the character is not similar then, dp[i][j] will be filled with 0.
- Similar substrings are consecutively placed together without any other characters and they will be the same for at most (j – i) characters. Hence, for valid substrings, dp[i][j] value must be greater than (j – i). Store those substrings in unordered_set which appears the maximum number of times consecutively.
- Finally, return the size of the unordered_set as the count of distinct substrings placed consecutively.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count the distinct substrings// placed consecutively in the given stringint distinctSimilarSubstrings(string str){ // Length of the string int n = str.size(); // If length of the string // does not exceed 1 if (n <= 1) { return 0; } // Initialize a DP-table vector<vector<int> > dp( n + 1, vector<int>(n + 1, 0)); // Stores the distinct substring unordered_set<string> substrings; // Iterate from end of the string for (int j = n - 1; j >= 0; j--) { // Iterate backward until // dp table is all computed for (int i = j - 1; i >= 0; i--) { // If character at i-th index is // same as character at j-th index if (str[i] == str[j]) { // Update dp[i][j] based on // previously computed value dp[i][j] = dp[i + 1][j + 1] + 1; } // Otherwise else { dp[i][j] = 0; } // Condition for consecutively // placed similar substring if (dp[i][j] >= j - i) { substrings.insert( str.substr(i, j - i)); } } } // Return the count return substrings.size();}// Driver Codeint main(){ string str = "neveropenneveropen"; cout << distinctSimilarSubstrings(str); return 0;} |
Java
// Java program to implement // the above approach import java.io.*;import java.util.ArrayList;class GFG{// Function to count the distinct substrings // placed consecutively in the given string static int distinctSimilarSubstrings(String str){ // Length of the string int n = str.length(); // If length of the string // does not exceed 1 if (n <= 1) return 0; // Initialize a DP-table long dp[][] = new long[n + 1][n + 1]; // Declaring ArrayList to store strings ArrayList<String> list = new ArrayList<String>(); // Iterate from end of the string for(int j = n - 1; j >= 0; j--) { // Iterate backward until // dp table is all computed for(int i = j - 1; i >= 0; i--) { // If character at i-th index is // same as character at j-th index if (str.charAt(i) == str.charAt(j)) { // Update dp[i][j] based on // previously computed value dp[i][j] = dp[i + 1][j + 1] + 1; } // Otherwise else { dp[i][j] = 0; } // Condition for consecutively // placed similar substring if (dp[i][j] >= j - i) { list.add(str.substring(j - i, i)); } } } // Return the count return list.size();}// Driver Codepublic static void main(String[] args){ String str = "neveropen"; System.out.println(distinctSimilarSubstrings(str));}}// This code is contributed by user_00 |
Python3
# Python3 program to implement # the above approach # Function to count the distinct substrings# placed consecutively in the given stringdef distinctSimilarSubstrings(str): # Length of the string n = len(str) # If length of the string # does not exceed 1 if(n <= 1): return 0 # Initialize a DP-table dp = [[0 for x in range(n + 1)] for y in range(n + 1)] # Stores the distinct substring substrings = set() # Iterate from end of the string for j in range(n - 1, -1, -1): # Iterate backward until # dp table is all computed for i in range(j - 1, -1, -1): # If character at i-th index is # same as character at j-th index if(str[i] == str[j]): # Update dp[i][j] based on # previously computed value dp[i][j] = dp[i + 1][j + 1] + 1 # Otherwise else: dp[i][j] = 0 # Condition for consecutively # placed similar substring if(dp[i][j] >= j - i): substrings.add(str[i : j - i]) # Return the count return len(substrings)# Driver Codestr = "neveropenneveropen"# Function callprint(distinctSimilarSubstrings(str))# This code is contributed by Shivam Singh |
C#
// C# program to implement // the above approach using System;using System.Collections.Generic;class GFG { // Function to count the distinct substrings // placed consecutively in the given string static int distinctSimilarSubstrings(string str) { // Length of the string int n = str.Length; // If length of the string // does not exceed 1 if (n <= 1) return 0; // Initialize a DP-table long[,] dp = new long[n + 1, n + 1]; // Declaring ArrayList to store strings List<string> list = new List<string>(); // Iterate from end of the string for(int j = n - 1; j >= 0; j--) { // Iterate backward until // dp table is all computed for(int i = j - 1; i >= 0; i--) { // If character at i-th index is // same as character at j-th index if (str[i] == str[j]) { // Update dp[i][j] based on // previously computed value dp[i, j] = dp[i + 1, j + 1] + 1; } // Otherwise else { dp[i, j] = 0; } // Condition for consecutively // placed similar substring if (dp[i, j] >= j - i) { list.Add(str.Substring(i, j - i)); } } } // Return the count return list.Count; } // Driver code static void Main() { string str = "neveropen"; Console.WriteLine(distinctSimilarSubstrings(str)); }}// This code is contributed by divyesh072019 |
Javascript
<script>// Javascript Program to implement// the above approach// Function to count the distinct substrings// placed consecutively in the given stringfunction distinctSimilarSubstrings(str){ // Length of the string var n = str.length; // If length of the string // does not exceed 1 if (n <= 1) { return 0; } // Initialize a DP-table var dp = Array.from(Array(n+1), ()=>Array(n+1).fill(0)); // Stores the distinct substring var substrings = new Set(); // Iterate from end of the string for (var j = n - 1; j >= 0; j--) { // Iterate backward until // dp table is all computed for (var i = j - 1; i >= 0; i--) { // If character at i-th index is // same as character at j-th index if (str[i] == str[j]) { // Update dp[i][j] based on // previously computed value dp[i][j] = dp[i + 1][j + 1] + 1; } // Otherwise else { dp[i][j] = 0; } // Condition for consecutively // placed similar substring if (dp[i][j] >= j - i) { substrings.add(str.substring(i, j)); } } } // Return the count return substrings.size;}// Driver Codevar str = "neveropenneveropen";document.write( distinctSimilarSubstrings(str));// This code is contributed by noob2000.</script> |
Output:
2
Time Complexity: O(N^2)
Auxiliary Space: O(N^2)
Efficient approach: Space optimization
In previous approach the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use two vectors curr and prev that keep track of current and previous row of DP.
Implementation Steps:
- Initialize a vectors prev of size N+1 to keep track of only previous row of Dp with 0.
- Now iterative over subproblems and get the current computation.
- While Initialize a vectors curr of size N+1 to keep track of only current row of Dp with 0.
- Now compute the current value by the help of prev vector and store that value in curr.
- After every iteration store values of curr vector in prev vector for further iterration.
- At last create substring and return its size.
Implementation:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to count the distinct substrings// placed consecutively in the given stringint distinctSimilarSubstrings(string str){ // Length of the string int n = str.size(); // If length of the string // does not exceed 1 if (n <= 1) { return 0; } // Initialize a previous row of dp-table vector<int> prev(n + 1, 0); // Stores the count of distinct substring unordered_map<string, int> substrings; // Iterate from end of the string for (int j = n - 1; j >= 0; j--) { // Initialize the current row of dp-table vector<int> cur(n + 1, 0); // Iterate backward until // dp table is all computed for (int i = j - 1; i >= 0; i--) { // If character at i-th index is // same as character at j-th index if (str[i] == str[j]) { // Update cur[i] based on // previously computed value cur[i] = prev[i + 1] + 1; } // Otherwise else { cur[i] = 0; } // Condition for consecutively // placed similar substring if (cur[i] >= j - i) { substrings[str.substr(i, j - i)]++; } } // Copy the current row to previous row prev = cur; } // Return the count return substrings.size();}// Driver Codeint main(){ string str = "neveropenneveropen"; cout << distinctSimilarSubstrings(str); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function to count the distinct substrings // placed consecutively in the given string public static int distinctSimilarSubstrings(String str) { // Length of the string int n = str.length(); // If length of the string does not exceed 1 if (n <= 1) { return 0; } // Initialize a previous row of dp-table int[] prev = new int[n + 1]; // Stores the count of distinct substring HashMap<String, Integer> substrings = new HashMap<>(); // Iterate from end of the string for (int j = n - 1; j >= 0; j--) { // Initialize the current row of dp-table int[] cur = new int[n + 1]; // Iterate backward until dp table is all computed for (int i = j - 1; i >= 0; i--) { // If character at i-th index is same as character at j-th index if (str.charAt(i) == str.charAt(j)) { // Update cur[i] based on previously computed value cur[i] = prev[i + 1] + 1; } // Otherwise else { cur[i] = 0; } // Condition for consecutively placed similar substring if (cur[i] >= j - i) { substrings.merge(str.substring(i, j), 1, Integer::sum); } } // Copy the current row to previous row prev = cur; } // Return the count return substrings.size(); } // Driver Code public static void main(String[] args) { String str = "neveropenneveropen"; System.out.println(distinctSimilarSubstrings(str)); }} |
Javascript
// Function to count the distinct substrings// placed consecutively in the given stringfunction distinctSimilarSubstrings(str) { // Length of the string let n = str.length; // If length of the string does not exceed 1 if (n <= 1) { return 0; } // Initialize a previous row of dp-table let prev = new Array(n + 1).fill(0); // Stores the count of distinct substring let substrings = {}; // Iterate from end of the string for (let j = n - 1; j >= 0; j--) { // Initialize the current row of dp-table let cur = new Array(n + 1).fill(0); // Iterate backward until dp table is all computed for (let i = j - 1; i >= 0; i--) { // If character at i-th index is same as character at j-th index if (str[i] == str[j]) { // Update cur[i] based on previously computed value cur[i] = prev[i + 1] + 1; } // Otherwise else { cur[i] = 0; } // Condition for consecutively placed similar substring if (cur[i] >= j - i) { substrings[str.substr(i, j - i)]++; } } // Copy the current row to previous row prev = cur; } // Return the count return Object.keys(substrings).length;}// Driver Codelet str = "neveropenneveropen";console.log(distinctSimilarSubstrings(str)); |
Output
2
Time Complexity: O(N^2)
Auxiliary Space: O(N)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
