C++-এ উৎপত্তি থেকে সবচেয়ে দূরে

ধরুন আমাদের একটি স্ট্রিং আছে যেখানে প্রতিটি অক্ষর হয় "L", "R" বা "?"৷ "L" মানে এক ইউনিট বামে সরানো হয়েছে, "R" মানে এক ইউনিট ডানে সরানো হয়েছে, এবং "?" মানে হয় "L" বা "R"। আমরা যদি 0 অবস্থানে থাকি, তাহলে "?" প্রতিস্থাপন করে আমাদের 0 থেকে সর্বোচ্চ সম্ভাব্য দূরত্ব খুঁজে বের করতে হবে। "L" বা "R" সহ।

সুতরাং, ইনপুট যদি "LLRRL??" এর মত হয়, তাহলে আউটপুট হবে 3, প্রতিস্থাপন? L ব্যবহার করে 5 ইউনিট বামে এবং 2 ইউনিট ডানে সরানো, তাই সর্বোচ্চ স্থানচ্যুতি হল 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• op :=0, l :=0, r :=0

• প্রতিটির জন্য এটি s −

  • যদি এটি 'L' এর মত হয়, তাহলে −

    • (l 1 দ্বারা বাড়ান)

  • অন্যথায় যখন এটি 'R' এর মতো হয়, তখন −

    • (1 দ্বারা r বাড়ান)

  • অন্যথায়

    • (1 দ্বারা op বাড়ান)

• সর্বোচ্চ (l এবং r) - সর্বনিম্ন (l এবং r) + op

  ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s) {
      int op = 0;
      int l = 0;
      int r = 0;
      for (auto &it : s) {
         if (it == 'L') {
            l++;
         } else if (it == 'R') {
            r++;
         } else {
            op++;
         }
      }
      return max(l, r) - min(l, r) + op;
   }
};
main() {
   Solution ob;
   cout << (ob.solve("LLRRL??"));
}

ইনপুট

"LLRRL??"

আউটপুট

3