Frontend School

Lexicographically Smallest Substring with Character Decrements

DSA
hard

Lexicographically Smallest Substring with Character Decrements

Hard
String
Greedy
Sliding Window
Binary Search
Hashing

Overview

In data compression and string processing, optimizing string representations for lexicographical order is crucial for efficient indexing, searching, and storage. This problem challenges you to find the lexicographically smallest substring of a given length after applying a limited number of character decrement operations. This scenario models real-world problems where data transformation costs are constrained, and optimal ordering is desired.

What you need to do / Task

Given a string S, a target substring length L, and a maximum allowed cost K, your task is to implement a function that returns the lexicographically smallest substring of S of length L that can be formed by applying at most K total decrement operations.

Here are the rules for decrement operations:

  • A decrement operation reduces a character c to c-1 (e.g., 'b' becomes 'a').
  • Each decrement operation costs 1.
  • The character 'a' cannot be decremented further.
  • The total cost across all characters in the substring must not exceed K.
  • To achieve the lexicographically smallest string, characters should be decremented greedily from left to right within the substring.

Input & output

Function Signature:

function findLexSmallestSubstring(s: string, L: number, K: number): string;

Input:

  • s: A string consisting of lowercase English letters.
  • L: An integer representing the required length of the substring.
  • K: An integer representing the maximum total cost allowed for character decrements.

Output:

  • A string representing the lexicographically smallest substring of length L obtainable under the given constraints.

Clarifications

  • The input string s will always contain lowercase English letters. There will be no empty strings.
  • If K is sufficiently large to transform any substring of length L into a string of all 'a's, then 'a' repeated L times is the answer.
  • The cost K is applied independently to each candidate substring. You choose one substring from S, apply transformations up to K cost, and then compare it with other transformed substrings.

Examples

1

Example 1

Input:

s = "dbca", L = 2, K = 1

Output:

"ac"

Note:

Original substrings of length 2:

  • "db": Cost to make 'd' to 'a' is 3. With K=1, 'd' becomes 'c'. 'b' remains 'b'. Transformed: "cb".
  • "bc": Cost to make 'b' to 'a' is 1. With K=1, 'b' becomes 'a'. 'c' remains 'c'. Transformed: "ac".
  • "ca": Cost to make 'c' to 'a' is 2. With K=1, 'c' becomes 'b'. 'a' remains 'a'. Transformed: "ba". Comparing "cb", "ac", "ba", the lexicographically smallest is "ac".
2

Example 2

Input:

s = "azby", L = 3, K = 2

Output:

"axb"

Note:

Original substrings of length 3:

  • "azb": Cost to make 'a' to 'a' is 0. Cost to make 'z' to 'a' is 25. With K=2, 'a' remains 'a'. We spend K=2 on 'z', making it 'x'. 'b' remains 'b'. Transformed: "axb".
  • "zby": Cost to make 'z' to 'a' is 25. With K=2, 'z' becomes 'x'. 'b' remains 'b', 'y' remains 'y'. Transformed: "xby". Comparing "axb" and "xby", "axb" is lexicographically smaller.
3

Example 3

Input:

s = "topcoder", L = 4, K = 10

Output:

"agde"

Note:

Let's consider the substring S[3...6] which is "code". Characters and their costs to become 'a': 'c'(2), 'o'(14), 'd'(3), 'e'(4). To make "code" lexicographically smallest with K=10:

  1. 'c' (at S[3]) becomes 'a'. Cost: 2. Remaining K: 8.
  2. 'o' (at S[4]) becomes 'g' ('o' - 8). Cost: 8. Remaining K: 0.
  3. 'd' (at S[5]) and 'e' (at S[6]) remain unchanged as K is exhausted. The transformed substring is "agde". This is the lexicographically smallest among all possible transformed substrings of length 4.

Constraints

Constraints & assumptions

  • 1 <= L <= s.length <= 2 * 10^5
  • 0 <= K <= s.length * 25 (Maximum possible cost if all characters are 'z' and L = s.length)
  • s consists only of lowercase English letters ('a' through 'z').

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies and applies the greedy strategy for character transformations and accurately compares candidate substrings.
  • Efficiency: The solution achieves optimal or near-optimal time complexity (O(N log L)), demonstrating an understanding of how to avoid O(N*L) brute-force comparisons.
  • Data Structures: Appropriate use of data structures (e.g., prefix sums, string hashing with LCP comparison) to optimize lookups and comparisons.
  • Edge Case Handling: The solution gracefully handles edge cases such as K=0, K being very large, and substrings near the string boundaries.

Loading editor...