Problem #402: Easy C++ solution with explanations
Solution\n\nThe main idea is that we go left to right because in numbers, left digits are more powerful. What do I mean? Consider 24 and 19. Which is bigger? 24
### Solution\n\nThe main idea is that we go left to right because in numbers, left digits are more powerful. What do I mean? Consider 24 and 19. Which is bigger? 24, of course, because 2 is more than 1. So even though 19 has a bigger second digit, that doesn\'t matter because the first digit is more powerful.\n\nThen we consider if we should delete each digit individually. If a digit is bigger than the next digit, we delete it. Consider "32169": if we keep the 3 and delete some future digit, we\'ll have a 4 digit number starting with 3. If we delete the 3, we\'ll have a 4 digit number starting with 2, which will be less regardless of the other digits. \n\nOne tricky thing is that when we delete a digit as described above, the following digit could again be eclipsed by the new previous digit. Consider "34561". We get through "3456" without deleting anything. Then we delete the 6 because it\'s bigger than the 1, but the new digit preceding 1 is 5. We didn\'t delete it earlier because it used to neighbor the 6, but now it neighbors the 1 so we should delete it. We handle this by moving backwards when we delete a digit so that we reconsider the previous digit.\n\nThat\'s the main idea but we also need to consider a few other things. We might get through the digits and not delete enough digits. Consider "12345" and k=2. We wouldn\'t delete any digits. So we would just delete the last 2 digits after our first pass through. We also need to trim leading zeros.\n\nWe could make this more efficient by avoiding so many erase() calls. We could use a stack like in the official solution. But I like this simple code.\n\n```cpp\nstring removeKdigits(string num, int k) {\n  for (int i = 0; k > 0 && i < num.size() - 1;) {\n    if (num[i] > num[i + 1]) {\n      num.erase(i, 1);\n      k--;             // we deleted 1 digit\n      if (i > 0) i--;  // re-consider old digit e.g. "341"\n    } else\n      i++;\n  }\n\n  if (k > 0) num.erase(num.size() - k, k);\n  while (num.size() > 0 && num[0] == \'0\') num.erase(0, 1);\n\n  return num.size() > 0 ? num : "0";\n}\n```
['C', 'C++']