medium
2 views

String Rank among SubStrings

Find the lexicographic rank of a string among all unique substrings of itself

Understand the Problem

Problem Statement

A string S is passed as the input. The program must generate the set (all unique) of all the substrings of S and then sort that set lexicographically. Now the program must print the rank of the string S in the new set formed.

Note:
– String S contains only lowercase English letters.
– Time complexity matters, optimize your algorithm

Constraints

  • String S contains only lowercase English letters (a-z)
  • Length of S is between 1 and 100 characters
  • Time complexity matters - algorithm should be optimized
  • All substrings must be unique in the final set
  • The set must be sorted lexicographically

Examples

Example 1
Input
eren
Output
5
Explanation

The lexicographically sorted set of unique substrings is: e, en, er, ere, eren, n, r, re, ren. The string 'eren' appears at position 5.

Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    char S[101];
    scanf("%s", S);
    int n = strlen(S);
    
    long long rank = 1;
    int used[26] = {0};
    
    for (int i = 0; i < n; i++) {
        int smaller_chars = 0;
        for (int j = 0; j < 26; j++) {
            if (j < (S[i] - 'a') && !used[j]) {
                smaller_chars++;
            }
        }
        
        rank += smaller_chars * (n - i);
        
        if (!used[S[i] - 'a']) {
            used[S[i] - 'a'] = 1;
        }
    }
    
    printf("%lld\n", rank);
    return 0;
}
Time:O(n²) where n is the length of the string
Space:O(1) - uses constant extra space for the used array
Approach:

The C solution uses a counting approach to determine the rank:

  1. Initialize rank to 1 (1-based indexing)
  2. For each character position i in the string:
    • Count how many characters lexicographically smaller than S[i] haven't been used yet
    • Multiply this count by the number of positions remaining (n-i) to get substrings starting with smaller characters
    • Mark the current character as used to avoid counting duplicates
  3. Print the final rank

This avoids generating all substrings explicitly and achieves O(n²) time complexity.

Visual Explanation

Loading diagram...
All Problems