Last Substring in Lexicographical Order - Practice Coding Problems

Last Substring in Lexicographical Order - Problem

Given a string s, return the last substring of s in lexicographical order.

A substring is a contiguous sequence of characters within a string. Lexicographical order is the order used in dictionaries - for strings, this means comparing character by character from left to right using their ASCII values.

The last substring lexicographically is the one that would appear last if all possible substrings were sorted in dictionary order.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcab"

› Output: "cab"

💡 Note: All substrings: "a", "ab", "abc", "abca", "abcab", "b", "bc", "bca", "bcab", "c", "ca", "cab", "a", "ab", "b". The lexicographically largest is "cab".

Example 2 — Single Character

$ Input: s = "leetcode"

› Output: "tcode"

💡 Note: Starting from 't' gives us "tcode" which is lexicographically larger than any substring starting with earlier characters like "l" or "e".

Example 3 — Descending Order

$ Input: s = "zab"

› Output: "zab"

💡 Note: The string starts with the largest character 'z', so the entire string "zab" is the lexicographically largest substring.

Constraints

1 ≤ s.length ≤ 4 × 10⁵
s contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s = "abcab"

Process

Find best starting position using two pointers

Output

Return suffix from best position: "cab"

Key Takeaway

🎯 Key Insight: Use two pointers to compare potential starting positions and eliminate inferior ones efficiently

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that we need to find the starting position that gives us the lexicographically largest suffix. The optimal approach uses two pointers to efficiently compare potential starting positions without generating all substrings. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Optimization	O(n)	O(1)	Use two pointers to compare potential starting positions efficiently
Brute Force - Generate All Substrings	O(n³ log n)	O(n³)	Generate all possible substrings and find the lexicographically largest one

Two Pointers Optimization — Algorithm Steps

Initialize two pointers at positions 0 and 1
Compare characters and extend the better position
When one position becomes inferior, move it past the current better position
Continue until one pointer reaches the end

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set pointers i=0, j=1

Compare

Compare substrings starting at i and j

Update

Move inferior pointer past current position

Code -

solution.c — C

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

char* solution(char* s) {
    int n = strlen(s);
    int i = 0;
    int j = 1;
    
    while (j < n) {
        int k = 0;
        // Compare substrings starting at i and j
        while (j + k < n && s[i + k] == s[j + k]) {
            k++;
        }
        
        if (j + k == n) {
            // Reached end, substring at j is suffix of substring at i
            break;
        } else if (s[i + k] < s[j + k]) {
            // Substring at j is lexicographically larger
            i = j;
            j++;
        } else {
            // Substring at i is lexicographically larger
            j = j + k + 1;
        }
    }
    
    int resultLen = n - i;
    char* result = malloc((resultLen + 1) * sizeof(char));
    strcpy(result, s + i);
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is examined at most twice by the two pointers

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables and result string

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler