মান লক্ষ্য করুন একটি n অক্ষরের স্ট্রিং S। অক্ষরগুলো হয় 'R' অথবা 'U'। একটি ২D প্লেনে, একটি রোবট ডানে বা উপরে যেতে পারে। যখন 'R' থাকে তখন সে ডানে যাবে এবং 'U' থাকলে উপরে যাবে। কিন্তু স্ট্রিংটি খুব বড়, আমরা স্ট্রিংটি ছোট করতে চাই। "RU" বা "UR" জোড়াটি ডায়াগোনাল মুভ "D"-র হিসেবে রিপ্লেস করা হবে। আমাদের ফাইনাল আপডেটেড রিডিউসড স্ট্রিং-এর দৈর্ঘ্য বের করতে হবে।
তাই, যদি ইনপুট হয় S = "RUURU", তবে আউটপুট হবে ৫, কারণ স্ট্রিংটি হবে "DUD"
ধাপসমূহ
এটি সমাধান করার জন্য, আমরা এই ধাপগুলো অনুসরণ করব −
ans := 0
n := size of S
for initialize i := 0, when i < n, update (increase i by 1), do:
if S[i] is not equal to S[i + 1], then:
(increase i by 1)
(increase ans by 1)
return ans
উদাহরণ
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখি −
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int ans = 0;
int n = S.size();
for (int i = 0; i < n; ++i){
if (S[i] != S[i + 1])
i++;
ans++;
}
return ans;
}
int main(){
string S = "RUURU";
cout << solve(S) << endl;
}
ইনপুট
"RUURU"
আউটপুট
3
