Remove Trailing Zeros From a String
EasyPrompt
Given a positive integer num represented as a string, return the integer num without trailing zeros as a string.
Example 1:
Input: num = "51230100"
Output: "512301"
Explanation: Integer "51230100" has 2 trailing zeros, we remove them and return integer "512301".Example 2:
Input: num = "123"
Output: "123"
Explanation: Integer "123" has no trailing zeros, we return integer "123".
Constraints:
1 <= num.length <= 1000numconsists of only digits.numdoesn't have any leading zeros.
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward approach is to use regular expressions to identify and remove the trailing zeros. A regex pattern can be crafted to match one or more '0' characters at the very end of the string.
Algorithm
- Define a regular expression pattern
0+$to match trailing zeros. - Use the string's built-in replacement function to replace all occurrences of the pattern with an empty string.
- Return the resulting string.
Walkthrough
The core idea is to leverage the string replacement functionality available in most programming languages, combined with a regular expression. The regular expression 0+$ is used. The 0+ part matches the character '0' one or more times, and the $ is an anchor that asserts the position at the end of the string. This pattern specifically targets sequences of one or more zeros that are at the end of the string. We then use a function like replaceAll() to substitute the matched pattern (the trailing zeros) with an empty string "". If there are no trailing zeros, the pattern won't match, and the original string will be returned unchanged.
class Solution { public String removeTrailingZeros(String num) { // The regex "0+$" matches one or more '0's at the end of the string. // replaceAll replaces this match with an empty string. return num.replaceAll("0+$", ""); }}Complexity
Time
O(N), where N is the length of the string. The regex engine needs to scan the string to find a match.
Space
O(N), where N is the length of the input string. This is because `replaceAll` creates a new string to store the result.
Trade-offs
Pros
Very concise and requires minimal code.
Highly readable for those familiar with regular expressions.
Cons
Can be less performant than a manual loop due to the overhead of compiling and executing the regular expression.
Might be less intuitive for developers not comfortable with regex.
A more optimal and fundamental approach is to manually find the index of the last non-zero character. We can iterate backward from the end of the string, stopping at the first character that is not a '0'. The resulting string is the substring from the beginning up to this character.
Algorithm
- Initialize an index
ito the last index of the string (num.length() - 1). - Loop backwards from
itowards 0. - In each iteration, check if the character at the current index
iis '0'. - If it is '0', continue to the previous character by decrementing
i. - If it is not '0', break the loop.
- After the loop, the index
iholds the position of the last non-zero digit. - Return the substring of
numfrom index 0 toi + 1.
Walkthrough
This method avoids the overhead of regular expressions by performing a simple linear scan. We start from the last character of the string and move towards the beginning. We maintain an index, let's call it endIndex, initialized to the last index of the string. We check if the character at endIndex is '0'. If it is, we decrement endIndex and repeat. We continue this as long as we are within the string's bounds and the character is '0'. The loop stops when we find a character that is not '0'. The final value of endIndex points to the last character that should be included in the result. The desired output is the substring of the original string from the beginning (index 0) up to and including endIndex.
class Solution { public String removeTrailingZeros(String num) { int i = num.length() - 1; // Loop backwards from the end of the string while (i >= 0 && num.charAt(i) == '0') { i--; } // The substring from the beginning to the last non-zero character. // i + 1 is used because substring's end index is exclusive. return num.substring(0, i + 1); }}Complexity
Time
O(N), where N is the length of the string. The while loop runs at most N times (for a string like "1000"). The `substring` operation also takes O(N) time to copy the characters into a new string.
Space
O(N) in Java, because `substring` creates a new string of length up to N. The auxiliary space used by the loop itself is O(1).
Trade-offs
Pros
Generally faster than the regex approach as it avoids the overhead of the regex engine.
The logic is explicit, direct, and easy to follow.
Cons
Requires slightly more lines of code than the regex one-liner.
Solutions
Solution
class Solution { public String removeTrailingZeros ( String num ) { int i = num . length () - 1 ; while ( num . charAt ( i ) == '0' ) { -- i ; } return num . substring ( 0 , i + 1 ); } }class Solution { public: string removeTrailingZeros ( string num ) { while ( num . back () == '0' ) { num . pop_back (); } return num ; } };class Solution : def removeTrailingZeros ( self , num : str ) -> str : return num . rstrip ( "0" )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.