Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1: Brute Force
3.1.
Code
3.2.
Complexity Analysis
3.2.1.
Time Complexity: O(N2)
3.2.2.
Space Complexity: O(N)
4.
Approach 2: Hashing
4.1.
Code
4.2.
Complexity Analysis
4.2.1.
Time Complexity: O(N*logN)
4.2.2.
Space Complexity: O(N)
5.
Frequently Asked Questions
5.1.
What is the time complexity of push() and pop() operations in the queue?
5.2.
What is a map in C++ STL?
5.3.
What is the complexity of operations in a map?
6.
Conclusion
Last Updated: Mar 27, 2024

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

Author Rhythm Jain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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 with big companies.

Also see, Data Structures

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 suffixes:

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

Recommended: Try the Problem Yourself before moving on to the solution

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 the time complexity of O(N2).

Space Complexity: O(N)

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

Also check out - Substr C++

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 suffixes, 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 a string and not a 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 suffixes 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.

 

Check out this problem - Longest Common Prefix

Frequently Asked Questions

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).

What is a map 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.

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.

Conclusion

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 interview concepts.

Recommended problems -

 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Connect Chords
Next article
Online Election
Live masterclass