Brute Force Approach
The naive approach to solve the above problem is to generate all the suffix of string ‘S’ and store it in an array, say, ‘ARR’. After generating all the suffix, sort all the suffix in increasing order. The string at index 0,i.e ARR[0] is the 1st rank string, ARR[1] is the 2nd rank string, and so on.
Program
#include <bits/stdc++.h>
using namespace std;
/* Generating all the suffix strings of string 'S'*/
void generateAllSuffixString(string &s, vector<string> &arr)
{
for (int i = 0; i < s.size(); i++)
{
/*Create Temporary string to store the string.*/
string temp;
for (int j = i; j < s.size(); j++)
{
temp += s[j];
}
arr.push_back(temp);
}
}
/* Define function for finding rank of all suffix strings.*/
void findRank(vector<string> &arr)
{
/*Sort the array 'ARR'*/
sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size(); i++)
{
cout << arr.size()  arr[i].size() << " ";
}
}
int main()
{
/*Taking string as an input.*/
string s;
cin >> s;
/*Creating an array 'ARR' to store all the suffix strings.*/
vector<string> arr;
/*Function Call.*/
generateAllSuffixString(s, arr);
findRank(arr);
return 0;
}
Input
aaaba
Output
4 0 1 2 3
Complexities
Time Complexity
O(N * N), where ‘N’ is the size of the string ‘S’.
Reason: Generating all the strings takes O(N * N) time, whereas sorting takes O(N * log(N)) time hence the former dominates the time complexity.
Space Complexity
O(N), where N is the size of the string.
Reason: For storing all the generated strings, we need an array of size N.
Read More  Time Complexity of Sorting Algorithms
FAQs

What is the suffix string?
A string ‘A’ is the suffix string of string ‘B’ if and only if there is a string S = BA. ‘B’ may or may not be an empty string.

What is the proper suffix?
A string is said to be the proper suffix of string ‘S’ if and only if it is the suffix of ‘S’ and not equal to ‘S’.

How many suffix strings will be possible for a string with length ‘N’?
There are total ‘N’ suffix strings that will be possible because there are total ‘N’ indexes where suffix string can have its starting index.

How can we reduce the time complexity of the above algorithm?
We can reduce the time complexity of the above algorithm by using the Ukkoken Tree algorithm.

Can we solve the above problem in O(1) extra space with the same time complexity?
No, it is not possible to solve the above problem with the same time complexity in O(1) time because storing all the generated suffix strings takes linear space complexity.
Key Takeaways
In this blog, we learned about an interesting problem based on String. We solved the problem using the brute force approach. Another problem involving string is: the smallest equivalent string
Check out this problem  Check If A String Is Palindrome
Hence learning never stops, and there is a lot more to learn.
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!