LeetCode Problem 3798

Difficulty: 🟢 Easy
Topics: String

Solution

LeetCode 3798 - Largest Even Number

Problem Understanding

We are given a string s that contains only the characters '1' and '2'. We are allowed to delete any number of characters while preserving the relative order of the remaining characters. In other words, we may choose any subsequence of the original string.

The goal is to produce the largest possible string that represents an even integer. Since the resulting string must be a subsequence, we cannot rearrange characters. We may only keep or remove characters.

An integer is even if its last digit is even. Since the string contains only '1' and '2', the resulting number is even if and only if its last character is '2'.

The key challenge is determining which characters to keep so that the resulting subsequence is numerically as large as possible while still ending with '2'.

The constraints are very small, 1 <= s.length <= 100, but even with small constraints we should still look for the simplest and most efficient solution.

Some important edge cases are:

• A string containing only '1' characters, in which case no even number can be formed.
• A string consisting entirely of '2' characters, where the entire string should be returned.
• A string where the only '2' appears very early, forcing us to discard everything after it.
• A string that already ends with '2', where keeping all characters may be optimal.
• A single-character string such as "1" or "2".

Approaches

Brute Force

A brute-force solution would generate every possible subsequence of the string.

For each subsequence, we would check whether:

1. It is non-empty.
2. It ends with '2'.
3. It represents a larger number than the best answer found so far.

Since a string of length n has 2^n subsequences, this approach becomes exponential. Even though n <= 100, generating all subsequences is completely infeasible.

The brute-force approach is correct because it explicitly examines every valid subsequence and selects the largest even one, but its running time is far too large.

Key Insight

Since the digits are only '1' and '2', the digit '2' is larger than '1'.

To maximize the resulting number, we want the longest possible sequence, and among sequences of equal length, we want larger digits to appear as early as possible.

The result must end with a '2'. Suppose we choose some occurrence of '2' as the final digit.

Any character before that chosen '2' can only help us:

• Adding more digits before the last digit increases the length.
• Keeping a digit never makes the number smaller when compared to deleting it, because longer positive integer strings are always numerically larger than their prefixes.

Therefore, once we decide which '2' will be the last digit, the optimal subsequence is simply the entire prefix ending at that '2'.

To maximize the result, we should choose the rightmost '2' in the string. This allows us to keep the largest possible prefix.

Thus the answer is simply the substring from the beginning of the string through the last occurrence of '2'.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n · n)	O(2^n · n)	Enumerates all subsequences
Optimal	O(n)	O(1)	Find the last '2' and return the prefix

Algorithm Walkthrough

1. Scan the string from right to left and find the last occurrence of the character '2'.
2. If no '2' exists, return the empty string. Any subsequence would consist entirely of '1' characters, which always form odd numbers.
3. Let the position of the rightmost '2' be last_two_index.
4. Return the substring s[:last_two_index + 1].
5. This substring contains every character up to and including the last '2', producing the longest possible valid even number.

Why it works

Any valid answer must end at some occurrence of '2'. If that occurrence is not the rightmost '2', then there are additional characters between it and the rightmost '2'. Keeping those characters and extending the subsequence to end at the rightmost '2' creates a longer number, which is always numerically larger. Therefore, the optimal answer must end at the rightmost '2', and keeping all preceding characters maximizes the result.

Python Solution

class Solution:
    def largestEven(self, s: str) -> str:
        last_two_index = s.rfind('2')

        if last_two_index == -1:
            return ""

        return s[:last_two_index + 1]

The implementation directly follows the algorithm.

The call to rfind('2') locates the rightmost occurrence of '2'. If no such character exists, rfind returns -1, indicating that no even number can be formed.

Otherwise, we return the prefix ending at that position. Because every character before the chosen ending digit can only increase the resulting number, this prefix is guaranteed to be optimal.

Go Solution

func largestEven(s string) string {
	lastTwoIndex := -1

	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == '2' {
			lastTwoIndex = i
			break
		}
	}

	if lastTwoIndex == -1 {
		return ""
	}

	return s[:lastTwoIndex+1]
}

The Go implementation performs the same logic manually. It scans from right to left until it finds the first '2', which is the rightmost occurrence in the string.

If no '2' is found, an empty string is returned. Otherwise, Go's string slicing operation returns the prefix ending at that index.

There are no concerns about integer overflow because we only manipulate indices. Returning "" is the standard way to represent an empty string in Go.

Worked Examples

Example 1

Input:

s = "1112"

Finding the rightmost '2':

Index	Character
3	2

last_two_index = 3

Returned substring:

s[:4] = "1112"

Output:

"1112"

Example 2

Input:

s = "221"

Scanning from the end:

Index	Character
2	1
1	2

last_two_index = 1

Returned substring:

s[:2] = "22"

Output:

"22"

Example 3

Input:

s = "1"

Scanning from the end:

Index	Character
0	1

No '2' is found.

last_two_index = -1

Output:

""

Additional Example

Input:

s = "2121121"

Scanning from the end:

Index	Character
6	1
5	2

last_two_index = 5

Returned substring:

s[:6] = "212112"

Output:

"212112"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One scan to locate the last '2'
Space	O(1)	Only a few variables are used

The algorithm performs a single traversal of the string. No auxiliary data structures are required, so the extra space usage remains constant.

Test Cases

sol = Solution()

assert sol.largestEven("1112") == "1112"      # provided example, already optimal
assert sol.largestEven("221") == "22"         # provided example
assert sol.largestEven("1") == ""             # provided example, no even number

assert sol.largestEven("2") == "2"            # single even digit
assert sol.largestEven("11") == ""            # all odd digits
assert sol.largestEven("22") == "22"          # all even digits

assert sol.largestEven("121") == "12"         # rightmost 2 in middle
assert sol.largestEven("2111") == "2"         # only 2 at beginning
assert sol.largestEven("112111") == "112"     # suffix after last 2 removed

assert sol.largestEven("2121121") == "212112" # mixed digits
assert sol.largestEven("222222") == "222222"  # many 2s
assert sol.largestEven("1111112") == "1111112" # last character is 2

# maximum-style length stress case
assert sol.largestEven("1" * 99 + "2") == "1" * 99 + "2"

Test Summary

Test	Why
"1112"	Already optimal answer
"221"	Requires deleting a trailing 1
"1"	No valid even number exists
"2"	Smallest valid even number
"11"	All digits are odd
"22"	All digits are even
"121"	Last 2 appears in the middle
"2111"	Only even digit at the start
"112111"	Must remove a long suffix
"2121121"	General mixed case
"222222"	Multiple possible ending positions
"1111112"	Rightmost character already even
"1"*99 + "2"	Near maximum input size

Edge Cases

No '2' Exists

A string such as "111111" contains only odd digits. Since an even number must end with an even digit, no valid subsequence exists. The implementation detects this because rfind('2') returns -1, and it immediately returns the empty string.

The Only '2' Is at the Beginning

Consider "21111". A common mistake would be to try preserving later digits because they increase length. However, any valid even number must still end with '2'. Since there is no later '2', the best answer is simply "2". Returning the prefix ending at the rightmost '2' handles this correctly.

The String Already Ends with '2'

For an input such as "121212", the rightmost '2' is already the last character. The algorithm returns the entire string unchanged. This is correct because deleting any character would either shorten the number or remove its even ending, producing a smaller result.

Multiple Occurrences of '2'

For a string like "21212", several positions could serve as the final digit. Choosing any earlier '2' would force us to discard characters that could otherwise be kept. By always selecting the rightmost '2', the algorithm guarantees the longest and therefore largest possible valid number.