मान लीजिए हमारे पास n अक्षरों वाली एक स्ट्रिंग S है। अक्षर या तो 'R' या 'U' हैं। एक 2D प्लेन पर, एक रोबोट दाएं या ऊपर जा सकता है। जब यह 'R' होता है तो यह दाएं जाता है और जब यह 'U' होता है तो यह ऊपर जाता है। हालांकि स्ट्रिंग बहुत बड़ी है, हम स्ट्रिंग को छोटा बनाना चाहते हैं। "RU" या "UR" जैसी जोड़ी को डायगोनल मूव "D" से बदल दिया जाएगा। हमें अंतिम अपडेटेड रिड्यूस्ड स्ट्रिंग की लंबाई ढूंढनी है।
इसलिए, यदि इनपुट S = "RUURU" है, तो आउटपुट 5 होगा, क्योंकि स्ट्रिंग "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