Count unique substrings of a string S present in a wraparound string

0 0 10 minutes read

Given a string S which is an infinite wraparound string of the string “abcdefghijklmnopqrstuvwxyz”, the task is to count the number of unique non-empty substrings of a string p are present in s.

Examples:

Input: S = “zab”
Output: 6
Explanation: All possible substrings are “z”, “a”, “b”, “za”, “ab”, “zab”.

Input: S = “cac”
Output: 2
Explanation: All possible substrings are “a” and “c” only.

Approach: Follow the steps below to solve the problem

Iterate over each character of the string
Initialize an auxiliary array arr[] of size 26, to store the current length of substring that is present in string S starting from each character of string P.
Initialize a variable, say curLen, which stores the length of substring present in P including the current character if the current character is not a part of the previous substring.
Initialize a variable, say ans, to store the unique count of non-empty substrings of p present in S.
Iterate over the characters of the string and check for the following two cases:
- Check if the current character can be added with previous substring to form the required substring or not.
- Add the difference of curLen and arr[curr] to ans if (curLen + 1) is greater than arr[curr] to avoid repetition of substrings.
Print the value of ans.

Below is the implementation of the above approach:

C++

// C++ program for
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of
// non-empty substrings of p present in s
int findSubstringInWraproundString(string p)
{
    // Stores the required answer
    int ans = 0;
 
    // Stores the length of
    // substring present in p
    int curLen = 0;
 
    // Stores the current length
    // of substring that is
    // present in string s starting
    // from each character of p
    int arr[26] = { 0 };
 
    // Iterate over the characters of the string
    for (int i = 0; i < (int)p.length(); i++) {
 
        int curr = p[i] - 'a';
 
        // Check if the current character
        // can be added with previous substring
        // to form the required substring
        if (i > 0
            && (p[i - 1]
                != ((curr + 26 - 1) % 26 + 'a'))) {
            curLen = 0;
        }
 
        // Increment current length
        curLen++;
 
        if (curLen > arr[curr]) {
 
            // To avoid repetition
            ans += (curLen - arr[curr]);
 
            // Update arr[cur]
            arr[curr] = curLen;
        }
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    string p = "zab";
 
    // Function call to find the
    // count of non-empty substrings
    // of p present in s
    findSubstringInWraproundString(p);
 
    return 0;
}

Java

import java.util.*;
class GFG 
{
   
    // Function to find the count of
    // non-empty substrings of p present in s
    static void findSubstringInWraproundString(String p)
    {
       
        // Stores the required answer
        int ans = 0;
 
        // Stores the length of
        // substring present in p
        int curLen = 0;
 
        // Stores the current length
        // of substring that is
        // present in string s starting
        // from each character of p
        int arr[] = new int[26];
 
        // Iterate over the characters of the string
        for (int i = 0; i < p.length(); i++)
        {
 
            int curr = p.charAt(i) - 'a';
 
            // Check if the current character
            // can be added with previous substring
            // to form the required substring
            if (i > 0
                && (p.charAt(i - 1)
                    != ((curr + 26 - 1) % 26 + 'a'))) 
            {
                curLen = 0;
            }
 
            // Increment current length
            curLen++;
            if (curLen > arr[curr])
            {
 
                // To avoid repetition
                ans += (curLen - arr[curr]);
 
                // Update arr[cur]
                arr[curr] = curLen;
            }
        }
 
        // Print the answer
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String p = "zab";
 
        // Function call to find the
        // count of non-empty substrings
        // of p present in s
        findSubstringInWraproundString(p);
    }
}
 
// This code is contributed by hemanth gadarla

Python3

# Python3 program for
# the above approach
 
# Function to find the count of
# non-empty substrings of p present in s
def findSubstringInWraproundString(p) :
 
    # Stores the required answer
    ans = 0
  
    # Stores the length of
    # substring present in p
    curLen = 0
  
    # Stores the current length
    # of substring that is
    # present in string s starting
    # from each character of p
    arr = [0]*26
  
    # Iterate over the characters of the string
    for i in range(0, len(p)) :
  
        curr = ord(p[i]) - ord('a')
  
        # Check if the current character
        # can be added with previous substring
        # to form the required substring
        if (i > 0 and (ord(p[i - 1]) != ((curr + 26 - 1) % 26 + ord('a')))) :
            curLen = 0
  
        # Increment current length
        curLen += 1
  
        if (curLen > arr[curr]) :
  
            # To avoid repetition
            ans += (curLen - arr[curr])
  
            # Update arr[cur]
            arr[curr] = curLen
  
    # Print the answer
    print(ans)
     
p = "zab"
  
# Function call to find the
# count of non-empty substrings
# of p present in s
findSubstringInWraproundString(p)
 
# This code is contributed by divyeshrabadiya07.

C#

// C# program for
// the above approach
using System;
class GFG 
{
 
  // Function to find the count of
  // non-empty substrings of p present in s
  static void findSubstringInWraproundString(string p)
  {
     
    // Stores the required answer
    int ans = 0;
 
    // Stores the length of
    // substring present in p
    int curLen = 0;
 
    // Stores the current length
    // of substring that is
    // present in string s starting
    // from each character of p
    int[] arr = new int[26];
 
    // Iterate over the characters of the string
    for (int i = 0; i < (int)p.Length; i++) 
    {
      int curr = p[i] - 'a';
 
      // Check if the current character
      // can be added with previous substring
      // to form the required substring
      if (i > 0 && (p[i - 1] != ((curr + 26 - 1) % 26 + 'a')))
      {
        curLen = 0;
      }
 
      // Increment current length
      curLen++;
      if (curLen > arr[curr])
      {
 
        // To avoid repetition
        ans += (curLen - arr[curr]);
 
        // Update arr[cur]
        arr[curr] = curLen;
      }
    }
 
    // Print the answer
    Console.Write(ans);
  }
 
  // Driver code
  static void Main() 
  {
    string p = "zab";
 
    // Function call to find the
    // count of non-empty substrings
    // of p present in s
    findSubstringInWraproundString(p);
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
    // Javascript program for the above approach
     
      // Function to find the count of
    // non-empty substrings of p present in s
    function findSubstringInWraproundString(p)
    {
 
      // Stores the required answer
      let ans = 0;
 
      // Stores the length of
      // substring present in p
      let curLen = 0;
 
      // Stores the current length
      // of substring that is
      // present in string s starting
      // from each character of p
      let arr = new Array(26);
      arr.fill(0);
 
      // Iterate over the characters of the string
      for (let i = 0; i < p.length; i++)
      {
        let curr = p[i].charCodeAt() - 'a'.charCodeAt();
 
        // Check if the current character
        // can be added with previous substring
        // to form the required substring
        if (i > 0 && (p[i - 1].charCodeAt() != ((curr + 26 - 1) % 26 + 'a'.charCodeAt())))
        {
          curLen = 0;
        }
 
        // Increment current length
        curLen++;
        if (curLen > arr[curr])
        {
 
          // To avoid repetition
          ans += (curLen - arr[curr]);
 
          // Update arr[cur]
          arr[curr] = curLen;
        }
      }
 
      // Print the answer
      document.write(ans);
    }
     
    let p = "zab";
  
    // Function call to find the
    // count of non-empty substrings
    // of p present in s
    findSubstringInWraproundString(p);
   
  // This code is contributed by surehs07.
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(1)

Method 2:

Approach Steps:

Initialize a dictionary to store the count of distinct substrings starting with each letter of the English alphabet.
Initialize the length of the longest increasing substring ending at each position in the given string ‘p’ to 0.
Iterate over the characters of ‘p’ and update the length of the longest increasing substring ending at each position using dynamic programming.
Update the count of distinct substrings starting with each letter of ‘p’ based on the length of the longest increasing substring ending at each position.
Return the sum of counts for all letters.

C++

#include <iostream>
#include <cstring>
using namespace std;
 
int countSubstringsInWraparoundString(string p) {
    // Initialize an array to store the count
    // of distinct substrings starting with each letter
    int count[26];
    memset(count, 0, sizeof(count));
     
    // Initialize the length of the longest increasing
    // substring ending at each position to 0
    int len_inc_substring[p.length()];
    memset(len_inc_substring, 0, sizeof(len_inc_substring));
     
    // Iterate over the characters of the string
    for (int i = 0; i < p.length(); i++) {
        // Update the length of the longest increasing
        // substring ending at the current position
        if (i > 0 && (p[i] - p[i-1] + 26) % 26 == 1) {
            len_inc_substring[i] = len_inc_substring[i-1] + 1;
        }
        else {
            len_inc_substring[i] = 1;
        }
             
        // Update the count of distinct substrings
        // starting with the current letter
        count[p[i]-'a'] = max(count[p[i]-'a'], len_inc_substring[i]);
    }
         
    // Return the sum of counts for all letters
    int total_count = 0;
    for (int i = 0; i < 26; i++) {
        total_count += count[i];
    }
    return total_count;
}
 
int main() {
    string p = "zab";
    cout << countSubstringsInWraparoundString(p) << endl; // Output: 6
    return 0;
}

Java

// Java code to count the number of distinct substrings in a wraparound string
 
import java.util.Arrays;
 
public class Main {
    public static int countSubstringsInWraparoundString(String p) {
        // Initialize an array to store the count
        // of distinct substrings starting with each letter
        int[] count = new int[26];
        Arrays.fill(count, 0);
         
        // Initialize the length of the longest increasing
        // substring ending at each position to 0
        int[] len_inc_substring = new int[p.length()];
        Arrays.fill(len_inc_substring, 0);
         
        // Iterate over the characters of the string
        for (int i = 0; i < p.length(); i++) {
            // Update the length of the longest increasing
            // substring ending at the current position
            if (i > 0 && (p.charAt(i) - p.charAt(i-1) + 26) % 26 == 1) {
                len_inc_substring[i] = len_inc_substring[i-1] + 1;
            }
            else {
                len_inc_substring[i] = 1;
            }
                 
            // Update the count of distinct substrings
            // starting with the current letter
            count[p.charAt(i)-'a'] = Math.max(count[p.charAt(i)-'a'], len_inc_substring[i]);
        }
             
        // Return the sum of counts for all letters
        int total_count = 0;
        for (int i = 0; i < 26; i++) {
            total_count += count[i];
        }
        return total_count;
    }
 
    public static void main(String[] args) {
        String p = "zab";
        System.out.println(countSubstringsInWraparoundString(p)); // Output: 6
    }
}

Python3

def countSubstringsInWraparoundString(p):
    # Initialize a dictionary to store the count
    # of distinct substrings starting with each letter
    count = {chr(i): 0 for i in range(ord('a'), ord('z')+1)}
     
    # Initialize the length of the longest increasing
    # substring ending at each position to 0
    len_inc_substring = [0] * len(p)
     
    # Iterate over the characters of the string
    for i in range(len(p)):
        # Update the length of the longest increasing
        # substring ending at the current position
        if i > 0 and (ord(p[i]) - ord(p[i-1])) % 26 == 1:
            len_inc_substring[i] = len_inc_substring[i-1] + 1
        else:
            len_inc_substring[i] = 1
             
        # Update the count of distinct substrings
        # starting with the current letter
        count[p[i]] = max(count[p[i]], len_inc_substring[i])
         
    # Return the sum of counts for all letters
    return sum(count.values())
 
# Test the function with a sample input
p = "zab"
print(countSubstringsInWraparoundString(p)) # Output: 6

C#

using System;
 
public class MainClass {
    public static int
    CountSubstringsInWraparoundString(string p)
    {
        // Initialize an array to store the count
        // of distinct substrings starting with each letter
        int[] count = new int[26];
        Array.Fill(count, 0);
 
        // Initialize the length of the longest increasing
        // substring ending at each position to 0
        int[] len_inc_substring = new int[p.Length];
        Array.Fill(len_inc_substring, 0);
 
        // Iterate over the characters of the string
        for (int i = 0; i < p.Length; i++) {
            // Update the length of the longest increasing
            // substring ending at the current position
            if (i > 0 && (p[i] - p[i - 1] + 26) % 26 == 1) {
                len_inc_substring[i]
                    = len_inc_substring[i - 1] + 1;
            }
            else {
                len_inc_substring[i] = 1;
            }
 
            // Update the count of distinct substrings
            // starting with the current letter
            count[p[i] - 'a'] = Math.Max(
                count[p[i] - 'a'], len_inc_substring[i]);
        }
 
        // Return the sum of counts for all letters
        int total_count = 0;
        for (int i = 0; i < 26; i++) {
            total_count += count[i];
        }
        return total_count;
    }
 
    public static void Main()
    {
        string p = "zab";
        Console.WriteLine(CountSubstringsInWraparoundString(
            p)); // Output: 6
    }
}

Javascript

function countSubstringsInWraparoundString(p) {
    // Initialize a dictionary to store the count
    // of distinct substrings starting with each letter
    let count = {};
    for (let i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) {
        count[String.fromCharCode(i)] = 0;
    }
     
    // Initialize the length of the longest increasing
    // substring ending at each position to 0
    let len_inc_substring = new Array(p.length).fill(0);
     
    // Iterate over the characters of the string
    for (let i = 0; i < p.length; i++) {
        // Update the length of the longest increasing
        // substring ending at the current position
        if (i > 0 && (p.charCodeAt(i) - p.charCodeAt(i-1) + 26) % 26 == 1) {
            len_inc_substring[i] = len_inc_substring[i-1] + 1;
        } else {
            len_inc_substring[i] = 1;
        }
         
        // Update the count of distinct substrings starting with the current letter
        count[p[i]] = Math.max(count[p[i]], len_inc_substring[i]);
    }
     
    // Return the sum of counts for all letters
    return Object.values(count).reduce((a,b) => a+b);
}
 
// Test the function with a sample input
let p = "zab";
console.log(countSubstringsInWraparoundString(p)); // Output: 6

Output

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the input string ‘p’. This is because we iterate over the characters of ‘p’ only once.

Auxiliary Space:

The auxiliary space of this approach is O(26), which is constant. This is because we use a dictionary to store the count of distinct substrings starting with each letter of the English alphabet, and the size of the dictionary is fixed at 26. We also use a list of size n to store the length of the longest increasing substring ending at each position in ‘p’. Therefore, the total auxiliary space used by the algorithm is O(26 + n), which is equivalent to 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 zambiatek!