3798. Largest Even Number

EasyString

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s consisting only of the characters '1' and '2'.

You may delete any number of characters from s without changing the order of the remaining characters.

Your task is to return the largest possible resultant string that represents an even integer. If no such string can be formed, return the empty string "".

A few important points to understand:

The string only contains the digits '1' and '2'. Since '2' is even and '1' is odd, an integer is even only when its last digit is '2'.
To make the resultant string as large as possible, you want to keep as many characters as you can. The more digits the number has, the larger it is. So ideally, you should only remove characters when absolutely necessary.
Because deletions cannot change the order of the remaining characters, the resulting string is always a subsequence of s.

To get the largest even number, you keep the entire string up to and including the last '2', and remove any trailing '1' characters that come after it. If there is no '2' in the string at all, then no even number can be formed, and you return "".

Example:

For s = "12211", the trailing '1' characters are removed, leaving "122", which is even and the largest possible result.
For s = "111", there is no '2', so the answer is "".

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Finding the last '2' and trimming trailing '1's to form the largest even number is a straightforward string manipulation.

Open in Flowchart

Intuition

The key observation is what makes a number even: its last digit must be even. Since this string only contains '1' and '2', the only even digit available is '2'. So the resultant string must end with a '2' to be even.

Next, we want the result to be as large as possible. A longer number is always larger than a shorter one, so our goal is to keep as many characters as we can. We should only delete characters when it is necessary to satisfy the "even" requirement.

Now think about which characters we actually need to remove. The original string already has all its digits in order. The only problem occurs if the string ends with one or more '1' characters, because then the last digit would be odd. To fix this, we simply strip off those trailing '1' characters until the string ends in '2'.

This naturally leads to the idea of removing all '1' characters from the right end of the string:

If the last character is already '2', nothing needs to be removed — the whole string is the answer.
If there are trailing '1's, we peel them off one by one until we reach a '2'.
If the entire string is made of '1's (no '2' anywhere), then stripping removes everything, leaving "", which correctly signals that no even number can be formed.

This means the answer is exactly the original string with its trailing '1' characters removed, which is precisely what s.rstrip("1") does.

Solution Approach

The implementation follows directly from the intuition: we need to remove all trailing '1' characters so that the string ends in '2' (making it even) while keeping it as long as possible.

Algorithm / Pattern Used:

This problem is solved with a string trimming technique. Rather than scanning and building a new string manually, we use Python's built-in str.rstrip method, which removes characters from the right end of a string.

Step-by-step walkthrough:

We call s.rstrip("1").
The rstrip("1") operation looks at the rightmost character of s. As long as that character is '1', it removes it and continues checking the new rightmost character.
The moment it encounters a '2' (or the string becomes empty), it stops.
The remaining string is returned as the result.

Why this works for every case:

If s ends in '2', rstrip("1") removes nothing and returns the full string — the largest possible even result.
If s ends in one or more '1's, those are peeled off until a '2' is exposed, giving the largest even subsequence.
If s is entirely '1's, every character is stripped away, returning "", which correctly indicates no even number can be formed.

Equivalent manual logic (what rstrip does internally):

i = len(s)
while i > 0 and s[i - 1] == '1':
    i -= 1
return s[:i]

Here i starts at the end and moves left while it sees '1'. The final slice s[:i] is the trimmed string.

Complexity Analysis:

Time Complexity: O(n), where n is the length of s. In the worst case (a string of all '1's), every character is examined once during trimming.
Space Complexity: O(n) for the resulting string that is returned. No extra auxiliary data structures are needed beyond the output.

This solution is optimal because we must at least look at the trailing characters to know where the last '2' is, and a single pass from the right achieves exactly that.

Example Walkthrough

Let's trace through the solution approach using the small example s = "12211".

Goal: Find the largest even number we can form by deleting characters (without reordering). Recall that an even number must end in '2', and a longer string is always larger, so we keep as much as possible.

Initial string:

Index:  0   1   2   3   4
Char:  '1' '2' '2' '1' '1'

Step 1 — Look at the rightmost character.

We start the trimming pointer i at the end of the string (i = 5, the length). We examine the character just to the left of i, which is index 4:

'1' '2' '2' '1' '1'
                 ^  index 4 is '1'  → remove it

It's '1' (an odd digit). If we kept it, the number would end in 1 and be odd. So we peel it off and move left: i = 4.

Step 2 — Check the new rightmost character.

Now we look at index 3:

'1' '2' '2' '1'
             ^  index 3 is '1'  → remove it

Still '1'. Peel it off and move left: i = 3.

Step 3 — Check again.

Now we look at index 2:

'1' '2' '2'
         ^  index 2 is '2'  → STOP

This is '2', an even digit. The string now ends in '2', so it represents an even number. We stop trimming here. The pointer rests at i = 3.

Step 4 — Return the result.

The final answer is the slice s[:3]:

Result: "122"

Verification:

"122" ends in '2', so it is even. ✅
We removed only the two trailing '1's — the minimum necessary — so it is the largest possible even subsequence. ✅

Using Python's built-in, this is simply:

"12211".rstrip("1")   # → "122"

Contrast with the all-'1' case: For s = "111", the pointer keeps moving left through every '1' until it reaches index 0. Nothing remains, so the result is "", correctly signaling that no even number can be formed.

Solution Implementation

1class Solution:
2    def largestEven(self, s: str) -> str:
3        # Remove trailing '1' characters from the string.
4        # Odd digits at the end prevent the number from being even,
5        # so stripping them yields the largest even-ending prefix.
6        return s.rstrip("1")
7```
8
9A few observations worth sharing:
10
11**Perspective 1 — Faithful rewrite (above):** This keeps the exact behavior of the original code, only modernizing style and adding documentation. It's the safest interpretation of "rewrite the above code."
12
13**Perspective 2 — Corrected logic:** If the true goal is to find the largest even number formed by the digits, stripping only `'1'` is insufficient. A more general version would strip *all* odd digits (`1, 3, 5, 7, 9`) from the right end until an even digit is reached:
14
15```python3
16class Solution:
17    def largestEven(self, s: str) -> str:
18        # Strip trailing odd digits so the result ends in an even digit,
19        # making the represented number even.
20        return s.rstrip("13579")
21

1class Solution {
2    /**
3     * Removes all trailing '1' characters from the input string
4     * and returns the remaining prefix.
5     *
6     * @param s the input string to process
7     * @return the substring with trailing '1' characters stripped off
8     */
9    public String largestEven(String s) {
10        // Start the index at the end of the string (length, not last index).
11        int endIndex = s.length();
12
13        // Move the index backward while the preceding character is '1'.
14        // This effectively trims all consecutive '1's from the tail.
15        while (endIndex > 0 && s.charAt(endIndex - 1) == '1') {
16            endIndex--;
17        }
18
19        // Return the prefix from the start up to (but excluding) endIndex.
20        return s.substring(0, endIndex);
21    }
22}
23

1class Solution {
2public:
3    string largestEven(string s) {
4        // Remove trailing '1' characters from the end of the string.
5        // An even binary number must end with '0', so any trailing '1's
6        // are stripped until the last character is '0' or the string is empty.
7        while (!s.empty() && s.back() == '1') {
8            s.pop_back();
9        }
10
11        // Return the remaining string, which represents the largest
12        // even prefix (ending in '0') or an empty string if none exists.
13        return s;
14    }
15};
16

1/**
2 * Removes all consecutive trailing '1' characters from the end of the input string.
3 *
4 * The regular expression /1+$/ matches one or more '1' characters anchored
5 * at the end of the string ($), and replace() substitutes that match with
6 * an empty string, effectively trimming the trailing run of '1's.
7 *
8 * @param s - The input string to process.
9 * @returns The input string with any trailing run of '1' characters removed.
10 */
11function largestEven(s: string): string {
12    // Match a sequence of one or more '1' characters at the end of the string
13    // and replace it with an empty string to strip the trailing '1's.
14    return s.replace(/1+$/, '');
15}
16

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string s. The rstrip("1") operation scans the string from the right end, removing trailing "1" characters. In the worst case (e.g., when all characters are "1" or none need to be stripped after a full scan), it inspects each character once, resulting in linear time.
Space Complexity: O(n), where n is the length of the input string s. Since strings in Python are immutable, rstrip("1") creates and returns a new string. In the worst case, the resulting string has nearly the same length as the original, requiring O(n) additional space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Stripping '1' from both ends instead of only the right end.

A frequent mistake is reaching for s.strip("1") instead of s.rstrip("1"). The strip method removes the target characters from both the left and right ends of the string, while we only want to remove the trailing odd digits.

# WRONG — removes leading '1's too
return s.strip("1")

For s = "11221", this produces:

s.strip("1") → "22" (incorrectly drops the leading '1's)
s.rstrip("1") → "1122" (correct)

Removing leading characters changes which subsequence we keep and yields a shorter number than necessary. Since a longer string represents a larger integer, dropping valid leading digits gives a wrong (smaller) answer. Always use rstrip so only the right end is trimmed.

Pitfall: Returning a sentinel value other than "" for the no-solution case.

When the string is all '1's, the expected output is the empty string "". Some implementations mistakenly return None, "0", or -1 to signal "no even number exists."

# WRONG — invents a sentinel that doesn't match the spec
result = s.rstrip("1")
return result if result else "0"

The problem explicitly requires "" when no even number can be formed. Conveniently, rstrip already returns "" when every character is stripped, so no extra handling is needed:

# CORRECT — rstrip naturally yields "" for all-'1' input
return s.rstrip("1")

Adding a special case not only deviates from the spec but also risks breaking downstream code that checks for an empty result with if not result.

Pitfall: Misjudging "largest" as a lexicographic or sorting problem.

It can be tempting to think that making the number "largest" means sorting the digits in descending order (e.g., placing all '2's first). This is incorrect because deletions cannot reorder characters — the result must remain a subsequence of s.

# WRONG — reorders digits, violating the subsequence constraint
return "".join(sorted(s, reverse=True)).rstrip("1")

For s = "121", sorting gives "211" → "2", but the valid largest even subsequence is "12". The original relative order must be preserved, so trimming from the right is the only correct operation.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering