iframe-proxy | Sunbelt Computer Software

History

93 lines (71 loc) · 1.69 KB

Raw

// @saorav21994

// Stack implementation

// TC : O(n)

// SC : O(n)

class Solution {

public String removeKdigits(String num, int k) {

Stack<Character> st = new Stack<>();

for (char ch : num.toCharArray()) {

while (!st.isEmpty() && st.peek() > ch && k > 0) {

st.pop();

k -= 1;

}

st.push(ch);

}

while (k > 0 && !st.isEmpty()) {

st.pop();

k -= 1;

}

StringBuilder sb = new StringBuilder();

while (!st.isEmpty()) {

sb.append(st.pop());

}

sb = sb.reverse();

// remove leading zeros

int i = 0;

for (char ch : sb.toString().toCharArray()) {

if (ch != '0')

break;

i += 1;

}

String res = sb.toString().substring(i, sb.length());

if (res == "" || res == null)

return "0";

return res;

}

class Solution {

// TC : O(n)

// SC : O(n)

public String removeKdigits(String num, int k) {

Stack<Character> st = new Stack<>();

int i=0;

for(;i<num.length() && k>0;){

while(k>0 && !st.isEmpty() && num.charAt(i)< st.peek()){

st.pop();

k--;

}

st.push(num.charAt(i));

i++;

}

while(!st.isEmpty() && k>0){

st.pop();

k--;

}

String ans = "";

while(!st.isEmpty()){

ans = st.pop() + ans;

}

ans = ans + num.substring(i, num.length());

// 0002000

i = 0;

while(i<ans.length()){

if(ans.charAt(i) == '0'){

i++;

} else {

break;

}

// "000000"

return ans.substring(i).length() == 0 ? "0" : ans.substring(i);

}

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

RemoveKDigits.java

Latest commit

History

RemoveKDigits.java

File metadata and controls