/*
Observation 1: our highest prioirty is to move the number that is at index 0, with index 1 being 0
For example, if we have 3004567 and we want to remove 1 digit, we defintely want to remove 3, so that we can
get rid of the following 2 zeros, ending up with 4567, which will always give us the biggest decrease
Observation 2: if there is no case of observation 1, then we want to remove the biggest number in the first ascenging sequence.
For example, if we have 234543, we want to remove the 5 first, since after 5 the number starts going down.
Observatino 3: if we have to remove more than 1 digit, every digit removal can use the same strategy, i.e we can use greedy algorithm here, aka not dp.
*/
public class Solution {
public String removeKdigits(String num, int k) {
//change to list
List<Character> list = new ArrayList<Character>();
for(char c : num.toCharArray()){
list.add(c);
}
//we need to remove k digits
for(int i = 0; i<k; i++){
int size = list.size();
//observation 1
if(size > 1 && list.get(1) == '0'){
list.remove(0);
while(!list.isEmpty() && list.get(0) == '0'){
list.remove(0);
}
}
//if no observation 1, use observation 2
if(size == list.size()){
for(int j = 0; j < size; j++){
if((j < size  1 && list.get(j) > list.get(j+1))  (j == size  1)){
list.remove(j);
break;
}
}
}
}
//generate output
if(list.size() == 0) return "0";
StringBuilder result = new StringBuilder();
for(Character c : list){
result.append(c);
}
return result.toString();
}
}
You only need 3 simple observations to solve this! Intuitive and well commented JAVA solution.


I think you can combine the observation1 with observation2 in a single inner loop like:
int size = list.size(); int j = 0; while(j<size1) { // remaining the leading zeros, and skipping nondescending orders if(list.get(j) <= list.get(j+1)  list.get(j) == '0') j++; else{ list.remove(j); break; } } if(j == size  1) list.remove(j);