Problem Statement
Given a string s containing digits and lowercase English letters, return the sum of all numbers present in it.
Each group of consecutive digits forms one number. Letters separate these numbers.
Example 1
Input: s = "123xyz"
Output: 123
Explanation: The string contains one number, 123, so the sum is 123.
Example 2
Input: s = "1xyz23"
Output: 24
Explanation: The numbers are 1 and 23. Their sum is 1 + 23 = 24.
Approach
Consecutive digits in a string form one complete number. For example, “a12b3” contains the numbers 12 and 3, so we must add these numbers rather than add each digit separately.
We only need to keep track of the current number being stored and the overall sum. Once a number ends, its individual digits no longer matter only its contribution to the sum matters. Therefore, we do not need to store all the extracted numbers or create a separate substring for each one.
Algorithm
Initialize
totalandcurrentto0, wheretotalstores the overall sum andcurrentkeeps track of the number being formed.Read the string from left to right, building a number whenever consecutive digits appear.
Extend the number by multiplying its current value by 10 and adding the numeric value of the next digit.
When a non-digit appears, add the completed number to
totaland reset thecurrentto zero so the next group of digits starts a new number.After reading the entire string, add any remaining number to the sum. This handles strings that end with a digit. Return the final sum.
Dry Run
Sum of the Numbers in a String
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the sum of all numbers formed by consecutive digits. int sumOfNumbers(const string& s) { int total = 0; int current = 0; for (char c : s) { if (c >= '0' && c <= '9') { // Shift existing digits left, then append the new digit. current = current * 10 + (c - '0'); } else { // A letter ends the number; reset for the next group. total += current; current = 0; } } // Include a number with no following letter to close it. total += current; return total; }};// Driver codeint main() { string s = "123xyz"; Solution sol; cout << sol.sumOfNumbers(s) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the length of the string. Each character is processed once.
Space Complexity: O(1), only the current number and the overall sum are stored. No additional array or substring is needed.
Interview follow-up Questions
No. Leading zeros do not affect its value. For example, “a007b03” contains the numbers 7 and 3, so the result is 10.
Be the first to add a comment.