एक द्विआधारी स्ट्रिंग वैकल्पिक बनाने के लिए हटाया जाने वाला न्यूनतम वर्ण


कठिनाई स्तर आसान
में अक्सर पूछा Coursera चौपाई वृद्धि MAQ ओ 9 के समाधान पॉकेट रत्न टैक्सी4श्योर
तार

समस्या का विवरण

एक बाइनरी दी स्ट्रिंगएक प्रोग्राम लिखें, जो इस स्ट्रिंग से कम से कम वर्णों की संख्या प्राप्त करेगा, ताकि यह वैकल्पिक हो जाए। ए बाइनरी स्ट्रिंग को वैकल्पिक कहा जाता है यदि लगातार 0 या 1 नहीं हैं

इनपुट प्रारूप

पहली पंक्ति जिसमें स्ट्रिंग "s" है।

आउटपुट स्वरूप

पहली पंक्ति में एक पूर्णांक मान होता है जो बाइनरी स्ट्रिंग वैकल्पिक बनाने के लिए हटाए जाने वाले वर्णों की संख्या का प्रतिनिधित्व करता है।

की कमी

  • 1 <= | s | <= 10 ^ 6
  • s [i] या तो 0 या 1 है

उदाहरण

0011
2

स्पष्टीकरण: दिए गए स्ट्रिंग "0011" में हमें इसे वैकल्पिक बनाने के लिए एक शून्य और एक 1 को हटाने की आवश्यकता है।

कलन विधि

1. दिए गए स्ट्रिंग s को बाएं से दाएं की ओर ले जाएं।

2. यदि वर्तमान चार्ट अगले चार्ट से अलग है तो बस अगले इंडेक्स पर जाएं।

3. और, हमें एक वर्ण को हटाने की आवश्यकता है।

कार्यान्वयन

बाइनरी स्ट्रिंग वैकल्पिक बनाने के लिए न्यूनतम वर्णों के लिए C ++ प्रोग्राम को हटा दिया जाए

#include <bits/stdc++.h>
using namespace std;

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int ans=0;
   for(int i=0;i<n-1;i++)
   {
       if(s[i]==s[i+1])
       {
           ans++;
       }
   }
   cout<<ans<<endl;
   return 0;
}

बाइनरी स्ट्रिंग वैकल्पिक बनाने के लिए न्यूनतम वर्ण के लिए जावा प्रोग्राम को हटा दिया जाए

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                char a[] = s.toCharArray();
    int n = s.length();
                int ans=0;
                for(int i=0;i<n-1;i++)
                {
                    if(a[i]==a[i+1])
                    {
                        ans++;
                    }
                }
                System.out.println(ans);
  } 
} 
00011101
4

जटिलता विश्लेषण

समय जटिलता

पर) जहां n दिए गए तार का आकार है "एस"। यहां हम केवल स्ट्रिंग को ट्रैस करते हैं और जांचते हैं कि क्या वर्तमान चार्ट अगले चार के बराबर है। यदि यह समान है तो एएनएस को बढ़ाएं अन्यथा अगले सूचकांक पर जाएं।

अंतरिक्ष जटिलता

यहां हम किसी भी सहायक स्थान का उपयोग नहीं करते हैं इसलिए अंतरिक्ष की जटिलता है ओ (1)। बस यहाँ हम एक पूर्णांक चर घोषित करते हैं जो द्विआधारी स्ट्रिंग वैकल्पिक बनाने के लिए हटाए जाने वाले वर्णों की संख्या को संग्रहीत करता है।