Length Of All Prefixes That Are Also The Suffixes Of The Given String

Rhythm Jain
Last Updated: May 13, 2022

Introduction

A string, like an integer or a floating-point unit, is a data type used in programming that is used to represent text or characters rather than numbers.

String questions are increasingly becoming popular among interview questions. Therefore it is necessary to master questions based on string applications to ace technical interviews of big companies.

Problem Statement

We are given a String, our task is to find and output the length of all the prefixes that are also the suffixes of the string given.

Example:

Assume we have the following string as input:

Input:

S = "ababababab"

Output:

2 4 6 8

Explanation:

We have the following prefixes that are also suffix:

  • “ab”
  • “abab”
  • “ababab”
  • “ababababab”

Approach 1: Brute Force

One obvious approach is that for every prefix of the string, we can check if there exists any suffix that is the same as the prefix. If true, we can output the length of the current string.

We can do so by maintaining a temporary string and for each iteration of the input string, we can add a character to the temporary string so that it will form the prefix and for each prefix, we can check if it exists as a suffix or not.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void countSamePrefixSuffix(string s)
{
       int n = s.length();
    // Stores the temporary prefix string
    string prefix = "";

    // Traverse the string S
    for (int i = 0; i < n - 1; i++)
    {

        // Add the current character
        // to the prefix string
        prefix.push_back(s[i]);

        // Store the suffix string of same length as prefix
        string suffix = s.substr(n - 1 - i, n - 1);

        // Check if prefix equals suffix
        if (prefix == suffix)
        {
            cout << prefix.size() << " ";
        }
    }
}

// Driver Code
int main()
{
    string S = "ababababab";
    countSamePrefixSuffix(S);
    return 0;
}

Output

2 4 6 8

Complexity Analysis

Time Complexity: O(N2)

Because for each iteration of the prefix, we also have additional work of creating a suffix of the same length as the prefix. That’s why the overall overhead adds up to O(N2) complexity.

Space Complexity: O(N)

Because at the end of the iteration, we would have a prefix string of length(N-1).

Approach 2: Hashing

In the naive approach, our time complexity increased because, for each prefix, we need to create a suffix of the same length. We can improve upon this extra overhead by maintaining a hashmap of prefix strings. Thus we can optimize the naive approach by first storing all the prefixes in a hashmap and then iterating over all suffixes and checking if the suffix is already present in the hashmap or not.

Rather than creating a Hashmap of strings, we can create a hashmap of a queue. This is because while creating suffix, we can improve efficiency by using a queue of characters rather than a string because when we will try to match with the prefix, we will first need to reverse the original suffix since when we iterate from the back, it will be in the reverse order. So, it might become inefficient if we use string and not queue.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void countSamePrefixSuffix(string s)
{
       int n = s.length();
    // HashMap to store the prefixes of the string
    map<queue<char>, int> count;
    // Iterate in the range [0, n - 2]
    queue<char> prefix, suffix;
    for (int i = 0; i < n - 1; i++)
    {

        // Add the current character to the prefix and suffix
        prefix.push(s[i]);
        suffix.push(s[i]);

        // Mark the prefix as 1 in the HashMap
        count[prefix] = 1;
    }
    suffix.push(s[n - 1]);
    //Now check for each suffix
    for (int i = 0; i < n - 1; i++)
    {

        // Remove the character from
        // the front of suffix queue to get the suffix string
        suffix.pop();

        // Check if the suffix is
        // present in HashMap or not
        if (count[suffix] == 1)
        {
            cout << suffix.size() << " ";
        }
    }
}

// Driver Code
int main()
{
    string S = "ababababab";
    int N = S.size();
    countSamePrefixSuffix(S);

    return 0;
}

Output:

8 6 4 2

Complexity Analysis

Time Complexity: O(N*logN)

Since we avoided extra work for creating suffix at each iteration of the prefix, we are just left with two loops that iterate over the length of the string. Thus O(N) + O(N) = 2*O(N) =O(N)

Also storing and accessing elements in a map have an overhead of log(N) time complexity when the map contains N elements. So for N iterations, the time complexity for the map is O(N*logN). Therefore total complexity leads to :

O(N) + O(N*logN)=O(N*logN)

Space Complexity: O(N)

Since we are using a queue that could store up to N characters.

Frequently Asked Questions

  1. What is the time complexity of push() and pop() operations in the queue?
    In a queue, the complexity of push(), and pop() operations depends upon the implementation of the queue. For the inbuilt STL queue, the complexity of push(), and pop(), both are O(1).
     
  2. What is a map is in C++ STL?
    Maps are associative containers for storing items in a mapped manner. Each element has a mapped value and a key value. The key values of the two mapped values cannot be the same.
     
  3. What is the complexity of operations in a map?
    A map in c++ STL is implemented using highly balanced binary search trees like Red-Black Trees or AVL Trees. So most of the operations take O(log N) time.

Key Takeaways

A map provides quick access to the value by utilizing the key. This property comes in handy when creating any type of index or reference. Second, the map assures that a key is unique across the whole data structure, which is a great way to avoid data duplication.

String and application of various data structures on strings are the most critical technical and coding interviews concepts.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think