मान लीजिए कि हमारे पास croakOfFrogs नामक एक स्ट्रिंग है, यह विभिन्न मेंढकों से "क्रोक" स्ट्रिंग के संयोजन का प्रतिनिधित्व करता है, एक ही समय में कई मेंढक क्रोक कर सकते हैं, इसलिए कई "क्रोक" मिश्रित होते हैं। हमें दी गई स्ट्रिंग में सभी क्रोक को समाप्त करने के लिए विभिन्न मेंढकों की न्यूनतम संख्या ज्ञात करनी होगी।
यहां एक वैध "क्रोक" का अर्थ है कि एक मेंढक क्रमिक रूप से 5 अक्षर 'c', 'r', 'o', 'a', 'k' उत्पन्न कर रहा है। मेंढक को एक क्रोक खत्म करने के लिए सभी पांच अक्षर उत्पन्न करने होते हैं। यदि स्ट्रिंग मान्य "क्रोक" स्ट्रिंग नहीं है तो -1 लौटाएं।
इसलिए, यदि इनपुट "crcoakroak" जैसा है, तो आउटपुट 2 होगा क्योंकि पहला मेंढक "crcoakroak" चिल्ला सकता है। दूसरा मेंढक बाद में "क्रकोक्रोक" चिल्ला सकता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक नक्शा परिभाषित करें मी
-
आकार की एक सरणी ch परिभाषित करें:5 इसे {'c', 'r', 'o', 'a', 'k'}
के साथ असाइन करें -
अस्थायी:=0, सेवानिवृत्त:=0
-
प्रत्येक तत्व के लिए c में s, करें
-
(m[c] 1 से बढ़ाएं)
-
मैक्सवैल:=एम[ch[0]]
-
इनिशियलाइज़ करने के लिए i:=0, जब i <5, अपडेट करें (i से 1 बढ़ाएँ), करें -
-
अगर maxVal
-
वापसी -1
-
-
मैक्सवैल :=एम[ch[i]]
-
-
यदि c, 'c' के समान है, तो -
-
(तापमान 1 से बढ़ाएं)
-
-
अन्यथा जब c 'k' के समान हो, तब -
-
(तापमान को 1 से घटाएं)
-
-
ret :=अधिकतम रिट और अस्थायी
-
-
इनिशियलाइज़ i के लिए:=1, जब i <5, अपडेट (i से 1 तक बढ़ाएँ), करें -
-
अगर m[ch[0]], m[ch[i]] के बराबर नहीं है, तो -
-
वापसी -1
-
-
-
वापसी रिट
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minNumberOfFrogs(string s) {
map<char, int> m;
char ch[5] = { 'c', 'r', 'o', 'a', 'k' };
int temp = 0;
int ret = 0;
for (auto& c : s) {
m[c]++;
int maxVal = m[ch[0]];
for (int i = 0; i < 5; i++) {
if (maxVal < m[ch[i]] || m[ch[i]] < 0) {
return -1;
}
maxVal = m[ch[i]];
}
if (c == 'c') {
temp++;
}
else if (c == 'k') {
temp--;
}
ret = max(ret, temp);
}
for (int i = 1; i < 5; i++) {
if (m[ch[0]] != m[ch[i]])
return -1;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.minNumberOfFrogs("crcoakroak"));
} इनपुट
"crcoakroak"
आउटपुट
2