How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Point72.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Point72 during technical interviews.

Find the Smallest String After One Decrement

Company: Point72

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a string `s` consisting only of lowercase English letters. You must perform exactly one operation: 1. Choose one non-empty contiguous substring of `s`. 2. Replace every character in that substring with the previous character in the alphabet. - For example, `b` becomes `a`, `c` becomes `b`, and so on. - The character `a` wraps around and becomes `z`. Return the lexicographically smallest string that can be obtained after exactly one operation. Example: ```text Input: s = "cbabc" Output: "baabc" ``` Explanation: Choose the substring `"cb"` and decrement it to `"ba"`, producing `"baabc"`.

Quick Answer: This question evaluates string manipulation, lexicographic ordering, and reasoning about local character transformations including wrap-around behavior.

You are given a non-empty string `s` consisting only of lowercase English letters. You must perform exactly one operation: 1. Choose one non-empty contiguous substring of `s`. 2. Replace every character in that substring with the previous character in the alphabet. - `b` becomes `a`, `c` becomes `b`, and so on. - `a` wraps around and becomes `z`. Return the lexicographically smallest string that can be obtained after exactly one operation. Lexicographical order is the same as dictionary order: a string is smaller if it has a smaller character at the first position where the two strings differ.

Constraints

1 <= len(s) <= 100000
s contains only lowercase English letters

Examples

Input: "cbabc"

Expected Output: "baabc"

Explanation: Start at the first character. Decrement the substring "cb" to "ba", giving "baabc", which is the smallest possible result.

Input: "abac"

Expected Output: "aaac"

Explanation: Skip the leading `a`. Decrement only the substring "b" to "a" and stop before the next `a`, producing "aaac".

Input: "aaaa"

Expected Output: "aaaz"

Explanation: Every operation must change at least one character, and changing any `a` makes it `z`. To keep the string as small as possible, change only the last character.

Input: "b"

Expected Output: "a"

Explanation: The only valid substring is the whole string. Decrement `b` to `a`.

Input: "aaab"

Expected Output: "aaaa"

Explanation: Skip the leading `a` characters and decrement the final `b` to `a`.

Hints

Earlier characters matter more in lexicographical order. Try to improve the leftmost possible position without making an earlier character worse.
Turning an `a` into `z` is usually harmful. What should you do with leading `a` characters, and what if the entire string is all `a`?

Quick Overview

This question evaluates string manipulation, lexicographic ordering, and reasoning about local character transformations including wrap-around behavior.