Using greedy without proof
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Move from brute-force thinking to an efficient approach using greedy strategy.
Given a string s consisting of lowercase English letters. Perform the following operation:
Return the lexicographically smallest string after performing the operation.
Example 1:
Input: s = "cbabc"
Output: "baabc"
Explanation:
Perform the operation on the substring starting at index 0, and ending at index 1 inclusive.
Example 2:
Input: s = "aa"
Output: "az"
Explanation:
Perform the operation on the last letter.
Example 3:
Input: s = "acbbc"
Output: "abaab"
Explanation:
Perform the operation on the substring starting at index 1, and ending at index 4 inclusive.
Example 4:
Input: s = "leetcode"
Output: "kddsbncd"
Explanation:
Perform the operation on the entire string.
Constraints:
1 <= s.length <= 3 * 105s consists of lowercase English lettersProblem summary: Given a string s consisting of lowercase English letters. Perform the following operation: Select any non-empty substring then replace every letter of the substring with the preceding letter of the English alphabet. For example, 'b' is converted to 'a', and 'a' is converted to 'z'. Return the lexicographically smallest string after performing the operation.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Greedy
"cbabc"
"aa"
"acbbc"
shifting-letters)lexicographically-smallest-string-after-applying-operations)lexicographically-smallest-string-after-operations-with-constraint)replace-question-marks-in-string-to-minimize-its-value)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2734: Lexicographically Smallest String After Substring Operation
class Solution {
public String smallestString(String s) {
int n = s.length();
int i = 0;
while (i < n && s.charAt(i) == 'a') {
++i;
}
if (i == n) {
return s.substring(0, n - 1) + "z";
}
int j = i;
char[] cs = s.toCharArray();
while (j < n && cs[j] != 'a') {
cs[j] = (char) (cs[j] - 1);
++j;
}
return String.valueOf(cs);
}
}
// Accepted solution for LeetCode #2734: Lexicographically Smallest String After Substring Operation
func smallestString(s string) string {
n := len(s)
i := 0
for i < n && s[i] == 'a' {
i++
}
cs := []byte(s)
if i == n {
cs[n-1] = 'z'
return string(cs)
}
j := i
for j < n && cs[j] != 'a' {
cs[j] = cs[j] - 1
j++
}
return string(cs)
}
# Accepted solution for LeetCode #2734: Lexicographically Smallest String After Substring Operation
class Solution:
def smallestString(self, s: str) -> str:
n = len(s)
i = 0
while i < n and s[i] == "a":
i += 1
if i == n:
return s[:-1] + "z"
j = i
while j < n and s[j] != "a":
j += 1
return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]
// Accepted solution for LeetCode #2734: Lexicographically Smallest String After Substring Operation
impl Solution {
pub fn smallest_string(s: String) -> String {
let mut cs: Vec<char> = s.chars().collect();
let n = cs.len();
let mut i = 0;
while i < n && cs[i] == 'a' {
i += 1;
}
if i == n {
cs[n - 1] = 'z';
return cs.into_iter().collect();
}
let mut j = i;
while j < n && cs[j] != 'a' {
cs[j] = ((cs[j] as u8) - 1) as char;
j += 1;
}
cs.into_iter().collect()
}
}
// Accepted solution for LeetCode #2734: Lexicographically Smallest String After Substring Operation
function smallestString(s: string): string {
const cs: string[] = s.split('');
const n: number = cs.length;
let i: number = 0;
while (i < n && cs[i] === 'a') {
i++;
}
if (i === n) {
cs[n - 1] = 'z';
return cs.join('');
}
let j: number = i;
while (j < n && cs[j] !== 'a') {
const c: number = cs[j].charCodeAt(0);
cs[j] = String.fromCharCode(c - 1);
j++;
}
return cs.join('');
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.