Leetcode 2710: Remove Trailing Zeros From a String

Input: The input consists of a string representing a positive integer without leading zeros.

Example: Input: num = "890000"

Constraints:

• 1 <= num.length <= 1000

• num consists only of digits.

• The integer represented by the string does not have leading zeros.

Output: Return the input string after removing any trailing zeros.

Example: Output: "89"

Constraints:

• The output should be the string representing the integer without trailing zeros.

Goal: Remove all trailing zeros from the string representation of the given integer.

Steps:

• Step 1: Start from the last character of the string and check if it is a '0'.

• Step 2: Continue checking characters until a non-zero character is found.

• Step 3: Slice the string to exclude all trailing zeros.

Goal: The string contains a positive integer with no leading zeros.

Steps:

• The string length is between 1 and 1000.

• Each character is a digit, and there are no leading zeros.

Assumptions:

• The input string will always represent a valid positive integer.

• Input: Input: num = "5403000"

• Explanation: The integer represented by the string '5403000' has three trailing zeros. After removing them, the resulting string is '5403'.

• Input: Input: num = "1000"

• Explanation: The string '1000' has three trailing zeros. After removing them, the output is '1'.

Approach: We can solve this problem efficiently by iterating through the string from the end to the beginning and removing all the '0' characters until a non-zero digit is encountered.

Observations:

• Trailing zeros can be identified by iterating from the end of the string.

• Removing trailing zeros does not require modifying the middle portion of the string.

• The solution should be efficient enough to handle strings with up to 1000 characters.

Steps:

• Step 1: Iterate through the string from the last character.

• Step 2: Count the number of consecutive '0' characters at the end of the string.

• Step 3: Slice the string to remove the trailing zeros and return the result.

Empty Inputs:

• The input will not be empty, as per the constraints.

Large Inputs:

• Ensure that the solution works for large input sizes up to 1000 characters.

Special Values:

• If the string is composed of only zeros (e.g., '0000'), the result should be an empty string or '0'.

Constraints:

• Ensure that the solution works correctly for inputs with varying numbers of trailing zeros.

string removeTrailingZeros(string num) {
    int n = num.size();
    int cnt = 0;
    int len;
    for( len = 1; len <= n; len++) {
        if(num[n - len] == '0') cnt++;
        else break;
    }
    return num.substr(0, n - cnt);
}

1 : Function Declaration

string removeTrailingZeros(string num) {

The function `removeTrailingZeros` is declared. It takes a string `num` as an input and returns a string with trailing zeros removed.

2 : Variable Initialization

    int n = num.size();

The variable `n` is initialized to the size of the input string `num`, representing the total number of characters in the string.

3 : Variable Initialization

    int cnt = 0;

Initialize `cnt` to zero. This variable will count the number of trailing zeros in the string.

4 : Variable Declaration

    int len;

Declare the variable `len` which will be used to iterate through the string from the end.

5 : Loop Setup

    for( len = 1; len <= n; len++) {

A `for` loop is set up to iterate from the last character of the string towards the beginning, checking for trailing zeros.

6 : Check for Trailing Zero

        if(num[n - len] == '0') cnt++;

If the current character (starting from the end) is a zero, increment the `cnt` variable to track the number of zeros.

7 : Break Condition

        else break;

If a non-zero character is found, break the loop as there are no more trailing zeros.

8 : Return Statement

    return num.substr(0, n - cnt);

Return the substring of `num` from the start to `n - cnt` to remove the trailing zeros.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the string, as we only need to traverse the string once.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) in the worst case when the string has to be modified or a new string is created to hold the result.

Leetcode 2710: Remove Trailing Zeros From a String

Explore →