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;
}

You can also try this code with Online C++ Compiler
Run Code
Output
2 4 6 8

You can also try this code with Online C++ Compiler
Run Code
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;
}

You can also try this code with Online C++ Compiler
Run Code
Output:
8 6 4 2

You can also try this code with Online C++ Compiler
Run Code
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!