Maximum Score After Splitting a String
Problem Statement
Yeh problem bolti hai ke ek string s hai jo bas 0s aur 1s se bani hai. Ab humein string ko do non-empty substrings mein split karna hai aur maximum score find karna hai.
Split karne ke baad, score nikalne ka tareeka yeh hai:
Left substring mein kitne 0s hain + Right substring mein kitne 1s hain
Example se samajhte hain:
Example 1: Input:
s = "011101"Sab tareekon se split kar ke score calculate karte hain:
left = “0” aur right = “11101”, score = 1 (left ke zeros) + 4 (right ke ones) = 5
left = “01” aur right = “1101”, score = 1 (left ke zeros) + 3 (right ke ones) = 4
left = “011” aur right = “101”, score = 1 (left ke zeros) + 2 (right ke ones) = 3
left = “0111” aur right = “01”, score = 1 (left ke zeros) + 1 (right ke ones) = 2
left = “01110” aur right = “1”, score = 2 (left ke zeros) + 1 (right ke ones) = 3
Maximum score hota: 5
Example 2: Input:
s = "00111"left = “00” aur right = “111”, score = 2 (left ke zeros) + 3 (right ke ones) = 5
Maximum score hota: 5
Example 3: Input:
s = "1111"left = “1” aur right = “111”, score = 0 (left ke zeros) + 3 (right ke ones) = 3
Maximum score hota: 3
Constraints:
String length 2 se 500 ke beech mein hona chahiye
Sirf ‘0’ aur ‘1’ characters ale string.
Maximum Score After Splitting a String
Jab humein ek binary string ko do non-empty substrings mein split karke maximum score find karna hai, to hum straightforward approach follow kar sakte hain. Yeh approach mein hum string ke 0s aur 1s count karte hain.
Steps yeh hain:
- Pehle hum saare 0s aur 1s count karte hain.
- Fir hum ek ek position pe split karne ke baad left aur right substrings bante hain usko dekhte hain.
- Left substring ke 0s aur right substring ke 1s count karte hain.
- Yeh counts se score nikalte hain.
- Har possible split ke baad maximum score store karte hain.
Step-by-Step Approach:
Count Total Ones: Pehla step yeh hai ke poori string mein total kitne ones hain unhe count karna. Yeh humein help karega yeh jaanne mein ke kisi bhi split ke baad right substring mein kitne ones rahenge.
Iterate Through the String: Agla step yeh hai ke string ko iterate karna. Is process mein hum left substring mein zeros ka count maintain karte hain. Har ek possible split point pe, hum score calculate kar sakte hain:
Score = (Left substring ke zeros ka count) + (Total ones - Left substring ke ones ka count)
Calculate Maximum Score: Poore iteration ke dauraan, hum maximum score ko track karte rahenge jo humein ab tak mila hai.
Example se clear karne ke liye:
Total Ones Count: String s = "011101" mein total 1s = 4
Iterate and Calculate Score:
Split s at position 1: left = "0", right = "11101", score = 1 (left ke 0s) + (4 - 0) = 5
Split s at position 2: left = "01", right = "1101", score = 1 (left ke 0s) + (4 - 1) = 4
Split s at position 3: left = "011", right = "101", score = 1 (left ke 0s) + (4 - 2) = 3
Split s at position 4: left = "0111", right = "01", score = 1 (left ke 0s) + (4 - 3) = 2
Split s at position 5: left = "01110", right = "1", score = 2 (left ke 0s) + (4 - 3) = 3
Maximum Score: Har split ke score ko compare karne ke baad, maximum score jo milta hai woh 5 hai.
Time Complexity:
O(n)O(n) ka matlab yeh hota hai ki problem ko solve karne ke liye jitna samay lagta hai woh string ke length pe depend karta hai. nn string ki length hai. Is algorithm mein hum do passes karte hain:
Ek pass mein hum total ones ko count karte hain (jitne bhi ‘1’ characters hain).
Doosre pass mein hum maximum score calculate karte hain.
Space Complexity:
Space Complexity O(1)O(1) ka matlab yeh hai ki ismein constant amount of extra space use hoti hai, chahe input kitna bhi bara ho jaye. Is case mein, hum sirf kuch variables use kar rahe hain jo constant space mein fit ho jaate hain.
Solution
var maxScore = function(s) {
let totalOnes = 0;
let maxScore = 0;
let leftZeros = 0;
// String mein total ones count karte hain
for (let char of s) {
if (char === '1') {
totalOnes++;
}
}
// String ko iterate karke maximum score find karte hain
for (let i = 0; i < s.length - 1; i++) { // length - 1 tak stop karte hain taaki right substring non-empty rahe
if (s[i] === '0') {
leftZeros++;
} else {
totalOnes--; // Right substring mein ones ki count kam karte hain
}
// Current split ke liye score calculate karte hain
let score = leftZeros + totalOnes;
maxScore = Math.max(maxScore, score);
}
return maxScore;
};
– Pehle hum total ones count kar rahe hain string mein.
Phir string ko split karne ke sabhi possible ways se iterate karte hain.
Har split mein, agar char ‘0’ hai, to leftZeros ko badha karte hain, aur agar ‘1’ hai to totalOnes ko kam karte hain.
Split ka score calculate karke, agar naya score maxScore se bada ho, to maxScore ko update kar dete hain.
Finally, maximum score return karte hain.
Solution
class Solution {
public:
int maxScore(string s) {
int zeros = 0, ones = 0;
for (char c : s) {
if (c == '0') zeros++; // agar character '0' hai, to zeros ko badhaate hain
else ones++; // agar character '1' hai, to ones ko badhaate hain
}
int maxScore = 0, leftZeros = 0, rightOnes = ones;
for (int i = 0; i < s.length() - 1; i++) { // length - 1 tak stop karte hain taaki right substring non-empty rahe
if (s[i] == '0') leftZeros++; // agar character '0' hai, to leftZeros ko badhaate hain
else rightOnes--; // agar character '1' hai, to rightOnes ko kam karte hain
max(maxScore, leftZeros + rightOnes); // har split ke liye max score calculate karte hain
}
return maxScore; // maximum score return karte hain
}
};
Count Zeros aur Ones: Pehle for loop mein, hum total zeros aur ones string mein count karte hain.
Initialize Variables: Fir hum maxScore ko 0, leftZeros ko 0 aur rightOnes ko total ones ki value set karte hain.
Iterate Through String: Dusre loop mein, hum string ko split karte hue iterate karte hain. Agar current character ‘0’ hai, to leftZeros ko increase karte hain. Agar ‘1’ hai, to rightOnes ko decrease karte hain. Har iteration mein, hum leftZeros aur rightOnes ka total score calculate karte hain aur maxScore ko update karte hain agar current split ka score zyada ho.
Return maxScore: Sabhi iterations ke baad, hum maxScore ko return karte hain.
