मान लीजिए हमारे पास croakOfFrogs नामक एक स्ट्रिंग है, यह अलग-अलग मेंढकों से "croak" स्ट्रिंग का संयोजन दर्शाती है, कई मेंढक एक साथ क्रोक कर सकते हैं, इसलिए कई "croak" मिश्रित हैं। हमें दी गई स्ट्रिंग में सभी क्रोक खत्म करने के लिए विभिन्न मेंढकों की न्यूनतम संख्या ढूंढनी है।
यहाँ एक वैध "croak" का अर्थ है कि एक मेंढक 5 अक्षर 'c', 'r', 'o', 'a', 'k' क्रमिक रूप से उत्पन्न कर रहा है। मेंढकों को एक क्रोक खत्म करने के लिए सभी पांच अक्षर उत्पन्न करने होंगे। यदि स्ट्रिंग वैध "croak" स्ट्रिंग नहीं है तो -1 लौटाएं।
इसलिए, यदि इनपुट है "crcoakroak", तो आउटपुट 2 होगा क्योंकि पहला मेंढक "crcoakroak" चिल्ला सकता है। दूसरा मेंढक बाद में "crcoakroak" चिल्ला सकता है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक मैप m परिभाषित करें
आकार 5 का एक ऐरे ch परिभाषित करें जिसे {'c', 'r', 'o', 'a', 'k'} असाइन करें
temp := 0, ret := 0
s के प्रत्येक एलिमेंट c के लिए, करें
(m[c] को 1 से बढ़ाएं)
maxVal := m[ch[0]]
i := 0 से शुरू करें, जब i < 5, i बढ़ाते हुए, करें -
यदि maxVal < m[ch[i]] या m[ch[i]] < 0, तो -
-1 लौटाएं
maxVal := m[ch[i]]
यदि c, 'c' के समान है, तो -
(temp को 1 से बढ़ाएं)
अन्यथा जब c, 'k' के समान है, तो -
(temp को 1 से घटाएं)
ret := max(ret, temp)
i := 1 से शुरू करें, जब i < 5, i बढ़ाते हुए, करें -
यदि m[ch[0]], m[ch[i]] के बराबर नहीं है, तो -
-1 लौटाएं
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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
