LeetCode 2710 - Remove Trailing Zeros From a String

The problem asks us to remove all trailing zeros from a string representing a positive integer. The input num is a string consisting only of digits with no leading zeros, and the length of the string is between 1 and 1000.

leetcodeeasystring

LeetCode Problem 2710

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to remove all trailing zeros from a string representing a positive integer. The input num is a string consisting only of digits with no leading zeros, and the length of the string is between 1 and 1000. The output should be a string representation of the same integer but without any zeros at the end. For example, "51230100" becomes "512301" because the two zeros at the end are removed, and "123" remains "123" since it has no trailing zeros.

Key points to note include that the input is guaranteed to be a positive integer, so we will never encounter an empty string or a string representing zero. Trailing zeros may range from none to almost the entire length of the string. The input can be very long, up to 1000 characters, so efficiency is important even though the operations themselves are simple.

Edge cases to consider include strings that consist entirely of zeros after a nonzero prefix, strings with no zeros at all, and strings that end with exactly one zero. These edge cases ensure that our algorithm correctly identifies and removes only the trailing zeros while preserving the rest of the number.

Approaches

The brute-force approach is straightforward: iterate from the end of the string toward the beginning, counting or skipping zeros until we find the first non-zero digit. Then, return the substring from the beginning up to that position. This approach works because it explicitly finds where the trailing zeros start and slices the string accordingly. However, it requires manual iteration, which is unnecessary in languages with built-in string methods.

A more optimal solution leverages the built-in string method rstrip in Python or slicing in Go. The key observation is that removing trailing zeros is equivalent to trimming all occurrences of '0' from the right end of the string. This approach is simple, readable, and efficient, as it avoids explicit loops and leverages optimized library methods.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Iterate from the end, find first non-zero, then slice
Optimal O(n) O(1) Use built-in string trimming function to remove trailing zeros

Algorithm Walkthrough

  1. Take the input string num and identify the characters that need to be removed from the end, which are all '0' characters.
  2. Starting from the rightmost character, move leftwards until the first non-zero character is encountered. This defines the boundary of the substring that should remain.
  3. Slice the string up to this boundary, excluding all trailing zeros.
  4. Return the resulting substring as the final output.

Why it works: The algorithm works because trailing zeros, by definition, appear consecutively at the end of the string. By finding the first non-zero character from the right, we are guaranteed to preserve all significant digits while removing exactly all trailing zeros.

Python Solution

class Solution:
    def removeTrailingZeros(self, num: str) -> str:
        return num.rstrip('0')

The implementation leverages Python's built-in rstrip method, which removes all occurrences of a given character from the end of a string. Here, we pass '0' to remove all trailing zeros. This single line directly implements the algorithm steps outlined above and handles all edge cases automatically.

Go Solution

func removeTrailingZeros(num string) string {
    i := len(num) - 1
    for i >= 0 && num[i] == '0' {
        i--
    }
    return num[:i+1]
}

In Go, strings are immutable, so we cannot remove characters in-place. We iterate from the end of the string backward until we encounter the first non-zero character. The slice num[:i+1] creates a new string containing all characters up to this point, effectively removing the trailing zeros. This approach mirrors the Python rstrip behavior manually.

Worked Examples

Example 1: num = "51230100"

Step i num[i] Action Result
Start 7 '0' Trailing zero, decrement i i = 6
Step 2 6 '0' Trailing zero, decrement i i = 5
Step 3 5 '1' Non-zero found, stop Slice num[:6]
Result - - Return "512301" "512301"

Example 2: num = "123"

Step i num[i] Action Result
Start 2 '3' Non-zero, stop Slice num[:3]
Result - - Return "123" "123"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Must examine each trailing character at most once
Space O(1) No extra space is used beyond slicing or iteration

Even though slicing in Go creates a new string, it is proportional to the length of the resulting string, which is acceptable. Python rstrip internally works in a similar manner but is optimized.

Test Cases

# Provided examples
assert Solution().removeTrailingZeros("51230100") == "512301"  # trailing zeros removed
assert Solution().removeTrailingZeros("123") == "123"  # no trailing zeros

# Edge cases
assert Solution().removeTrailingZeros("10") == "1"  # single trailing zero
assert Solution().removeTrailingZeros("1000") == "1"  # multiple trailing zeros
assert Solution().removeTrailingZeros("1") == "1"  # single digit, no zeros
assert Solution().removeTrailingZeros("1203040500") == "12030405"  # multiple non-zero digits with trailing zeros
Test Why
"51230100" Regular case with multiple trailing zeros
"123" No trailing zeros
"10" Single trailing zero
"1000" Multiple trailing zeros
"1" Single-digit number, no zeros
"1203040500" Mixed digits with trailing zeros

Edge Cases

One important edge case is when the input string has a single digit, like "1". The algorithm must not remove any digits, and both Python and Go solutions handle this naturally. Another edge case is when the number has only one non-zero digit followed by multiple zeros, such as "1000". Our solutions correctly remove all trailing zeros, leaving "1".

A third edge case is numbers with intermittent zeros but ending with zeros, like "1203040500". It is crucial that the algorithm only removes the zeros at the end without affecting zeros in the middle of the string. Both Python's rstrip and the manual Go loop maintain all internal zeros correctly.

All solutions handle these cases consistently, ensuring the output preserves the numerical value of the original string without any trailing zeros.