ধরুন আমাদের একটি নন-নেগেটিভ ইন্টিজার num আছে যা স্ট্রিং হিসেবে রিপ্রেজেন্ট করা হয়েছে। আমাদের num থেকে k ডিজিট রিমুভ করতে হবে যাতে নতুন সংখ্যাটি সম্ভাব্য সবচেয়ে ছোট হয়। ইনপুট “1432219” এবং k = 3 হলে রেজাল্ট হবে “1219”।
সমাধানের ধাপগুলো:
একটি স্ট্যাক st ডিফাইন করুন, একটি খালি স্ট্রিং ret তৈরি করুন
n := num-এর সাইজ
i = 0 থেকে n – 1 পর্যন্ত লুপ চালান
যখন k নন-জিরো এবং স্ট্যাক খালি নয় এবং st-এর টপ > num[i]
স্ট্যাক থেকে পপ করুন এবং k ১ কমান
num[i] st-এ পশ করুন
যখন k 0 নয়, স্ট্যাক থেকে এলিমেন্ট পপ করুন
যখন স্ট্যাক খালি নয়
ret := ret + st-এর টপ, স্ট্যাক থেকে এলিমেন্ট পপ করুন
এখন ret স্ট্রিং রিভার্স করুন
ans := খালি স্ট্রিং, i := 0
যখন i < ret-এর সাইজ এবং ret[i] != '0'
i ১ বাড়ান
i < ret-এর সাইজ পর্যন্ত লুপ চালান
ans := ans + ret[i]
ret := ans
যদি ret-এর সাইজ 0 হয় তবে "0" রিটার্ন করুন, অন্যথায় ret
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
class Solution { public: string removeKdigits(string num, int k) { stack st; string ret = ""; int n = num.size(); for(int i = 0; i < n; i++){ while(k && !st.empty() && st.top() > num[i]){ st.pop(); k--; } st.push(num[i]); } while(k--)st.pop(); while(!st.empty()){ ret += st.top(); st.pop(); } reverse(ret.begin(), ret.end()); string ans = ""; int i = 0; while(i <ret.size() && ret[i] == '0')i++; for(; i < ret.size(); i++)ans += ret[i]; ret = ans; return ret.size() == 0? "0" : ret; } };
ইনপুট
"1432219" 3
আউটপুট
"1219"
