Table of contents
1.
Introduction
2.
The Problem Statement
2.1.
Example
3.
Brute Force Approach 
3.1.
Program
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Suffix String Rank Problem

Author Ujjawal Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

One day, the ninja's teacher gave him an assignment where he had given a string. His task was to find the index where the suffix has particular rank starts. Your task is to help ninja.

The above problem is the standard String problem. String based-coding problems are widely asked in coding contests and various coding interviews. Here we will discuss the naive approach.

The Problem Statement

Given a string, ‘S’ consists of only lower case alphabets. Your task is to find the index of the string where the suffix having rank ‘i’ starts (0<= I < |S|). Print the starting index of all the suffix(0 based indexing) of ‘S’ to increase their rank.

Note: Rank of string S1 is less than the rank of string S2 if S1 is lexicographically smaller than S2.

Example

Suppose S = “ninja”, then all the suffix of the string ‘S’ is as follows:

  • “a”, starting index 4.
  • “ja”, starting index 3.
  • “nja”, starting index 2.
  • “inja”, starting index 1.
  • “ninja”, starting index 0.
     

Lexicographically smaller order of all the above suffix strings are as follows:

  1. “a”.
  2. “inja”.
  3. “ja”.
  4. “ninja”.
  5. “nja”.
     

Hence its output is {4,1,3,0,2}.

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


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

  1. 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.
     
  2. 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’.
     
  3. 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.
     
  4. 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.
     
  5. 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!

Live masterclass