C++ में स्ट्रिंग में संतुलन स्थितियों की संख्या ढूंढें

मान लीजिए हमारे पास एक स्ट्रिंग है। हमें उस स्ट्रिंग में संतुलन स्थिति की गिनती ढूंढनी है जहां से स्ट्रिंग का बायां और दायां भाग समान वर्ण रखता है। वर्णों की आवृत्ति मायने नहीं रखती। तो यदि स्ट्रिंग "ABAABA" है, तो संतुलन स्थितियों की संख्या 3 है। ये स्थितियां AB|AABA, ABA|ABA, ABAA|BA हैं।

इसे हल करने के लिए, हम कुछ कुशल दृष्टिकोण का पालन करेंगे। स्ट्रिंग को ट्रैवर्स करने के बाद हम पहले right[] को सभी वर्णों की गिनती से भरते हैं। फिर स्ट्रिंग को बाएं से दाएं ट्रैवर्स करें। प्रत्येक वर्ण के लिए हम left[] में इसकी गिनती बढ़ाते हैं और right में गिनती घटाते हैं। ट्रैवर्स किए जा रहे किसी भी बिंदु के लिए, यदि सभी वर्ण जिनके left में शून्येतर मान हैं, उनके right में भी शून्येतर मान हैं, और इसके विपरीत भी सत्य है। तो परिणाम बढ़ाएं।

उदाहरण

#include <iostream> 
#include <algorithm> 
#define MAX_CHAR 256 
using namespace std; 

int countBalancePoints(string str) { 
    int left[MAX_CHAR] = {0}; 
    int right[MAX_CHAR] = {0}; 
    
    for (int i = 0; i < str.length(); i++) 
        right[str[i]]++; 
    
    int count = 0; 
    
    for (int i = 0; i < str.length(); i++) { 
        left[str[i]]++; 
        right[str[i]]--; 
        
        int j; 
        for (j = 0; j < MAX_CHAR; j++) { 
            if ((left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0)) 
                break; 
        } 
        
        if (j == MAX_CHAR) 
            count++; 
    } 
    
    return count; 
} 

int main() { 
    char str[] = "ABAABA"; 
    cout << "Number of balance points: " << countBalancePoints(str); 
}

आउटपुट

Number of balance points: 3