ಸ್ಟ್ರಿಂಗ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ವಿಭಜಿಸಿದ ನಂತರ ಗರಿಷ್ಠ ಸ್ಕೋರ್


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್
ಸ್ಟ್ರಿಂಗ್

ವಿಭಜನೆಯ ನಂತರ ಗರಿಷ್ಠ ಸ್ಕೋರ್ ಸಮಸ್ಯೆ a ಸ್ಟ್ರಿಂಗ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಮಗೆ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಒದಗಿಸಿದೆ. ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್ ಕೇವಲ 0 ಮತ್ತು 1 ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಇದನ್ನು ಬೈನರಿ ಅನುಕ್ರಮವೆಂದು ಸಹ ಪರಿಗಣಿಸಬಹುದು. ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ವಿಭಜಿಸಿದ ನಂತರ ಸಾಧಿಸಬಹುದಾದ ಗರಿಷ್ಠ ಸ್ಕೋರ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ನಮ್ಮನ್ನು ಕೇಳಿದೆ. ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ವಿಭಜಿಸಿದ ನಂತರ, ಸ್ಕೋರ್ ಅನ್ನು ಎಡ ಭಾಗದಲ್ಲಿ 0 ಸೆ ಸಂಖ್ಯೆ ಮತ್ತು ಬಲ ಅರ್ಧದಲ್ಲಿ 1 ಸೆ ಸಂಖ್ಯೆ ಎಂದು ಮೌಲ್ಯಮಾಪನ ಮಾಡಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ಎಂದಿನಂತೆ, ದ್ರಾವಣಕ್ಕೆ ಧುಮುಕುವ ಮೊದಲು. ನಾವು ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

s = "011101"
5

ವಿವರಣೆ: ಮೊದಲ ಸೂಚ್ಯಂಕದ ನಂತರ ನಾವು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ವಿಭಜಿಸಿದರೆ ಸಾಧ್ಯವಾದಷ್ಟು ಗರಿಷ್ಠ ಸ್ಕೋರ್ ಪಡೆಯಬಹುದು ಎಂದು ಒಬ್ಬರು ಸುಲಭವಾಗಿ ನೋಡಬಹುದು. ಆ ರೀತಿಯಲ್ಲಿ ನಾವು ಬಲ ಅರ್ಧದಲ್ಲಿ ನಾಲ್ಕು 1 ಸೆ ಮತ್ತು ಎಡಾರ್ಧದಲ್ಲಿ ಒಂದೇ 0 ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ.

ಸ್ಟ್ರಿಂಗ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ವಿಭಜಿಸಿದ ನಂತರ ಗರಿಷ್ಠ ಸ್ಕೋರ್

s = "00111"
5

ವಿವರಣೆ: ನಾವು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ವಿಭಜಿಸಿದರೆ ಎಡ ಅರ್ಧವು ಎಲ್ಲಾ 0 ಸೆಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಉಳಿದ ಅರ್ಧವು ಎಲ್ಲಾ 1 ಸೆಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಒಬ್ಬರು ಸುಲಭವಾಗಿ ಕಂಡುಹಿಡಿಯಬಹುದು. ಆ ರೀತಿಯಲ್ಲಿ ನಾವು ಗರಿಷ್ಠ ಸ್ಕೋರ್ ಪಡೆಯುತ್ತೇವೆ. ಆದ್ದರಿಂದ, ವಿಭಜನೆಯ ಹಂತವು ಸೂಚ್ಯಂಕ 2 ರಲ್ಲಿರಬೇಕು ಎಂದು ನೋಡುವುದು ಸುಲಭ.

ಸ್ಟ್ರಿಂಗ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ವಿಭಜಿಸಿದ ನಂತರ ಗರಿಷ್ಠ ಸ್ಕೋರ್‌ಗಾಗಿ ಅನುಸಂಧಾನ

ಸ್ಟ್ರಿಂಗ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ವಿಭಜಿಸಿದ ನಂತರ ಗರಿಷ್ಠ ಸ್ಕೋರ್ ಸಮಸ್ಯೆ ಸಮಸ್ಯೆಯ ವಿವರಣೆಯಲ್ಲಿ ಈಗಾಗಲೇ ಮೇಲೆ ತಿಳಿಸಲಾಗಿದೆ. ಸಂಕ್ಷಿಪ್ತವಾಗಿ, ನಾವು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಿದರೆ ಸಾಧಿಸಬಹುದಾದ ಗರಿಷ್ಠ ಸ್ಕೋರ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ನಮ್ಮನ್ನು ಕೇಳಿದೆ. ಎಡ ಅರ್ಧದಲ್ಲಿ 0 ಸೆ ಮತ್ತು ಬಲ ಅರ್ಧದಲ್ಲಿ 1 ಸೆ ಸಂಖ್ಯೆಯ ಪ್ರಕಾರ ಸ್ಕೋರ್ ಅನ್ನು ಮೌಲ್ಯಮಾಪನ ಮಾಡಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, ಮೊದಲು, ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿರುವ ಒಟ್ಟು ಸೊನ್ನೆಗಳು ಮತ್ತು ಬಿಡಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಲೆಕ್ಕ ಹಾಕುತ್ತೇವೆ. ಎರಡನೆಯ ಲೂಪ್‌ನಲ್ಲಿ, ನಾವು ಇಲ್ಲಿಯವರೆಗೆ ಎದುರಿಸಿದ 0f 0 ಸೆ ಸಂಖ್ಯೆಯನ್ನು ಲೆಕ್ಕ ಹಾಕುತ್ತಲೇ ಇರುತ್ತೇವೆ.

ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ವಿಭಜಿಸುವ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಅನುಕರಿಸಲು ನಾವು ಈ ಲೂಪ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ. ನಾವು ಇಲ್ಲಿಯವರೆಗೆ ಎದುರಿಸಿದ ಸೊನ್ನೆಗಳು ಮತ್ತು ಅವುಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಎಡಾರ್ಧದಲ್ಲಿ 1 ಸೆ ಸಂಖ್ಯೆಯನ್ನು ಕಳೆಯುವುದರ ಮೂಲಕ ಬಲ ಅರ್ಧದಲ್ಲಿರುವವರನ್ನು ಸುಲಭವಾಗಿ ಲೆಕ್ಕಹಾಕಬಹುದು. ನಾವು ಸಾಧಿಸಬಹುದಾದ ಗರಿಷ್ಠ ಮೌಲ್ಯದೊಂದಿಗೆ ಉತ್ತರವನ್ನು ನವೀಕರಿಸುತ್ತಲೇ ಇರುತ್ತೇವೆ.

ಸ್ಟ್ರಿಂಗ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ವಿಭಜಿಸಿದ ನಂತರ ಗರಿಷ್ಠ ಸ್ಕೋರ್‌ಗಾಗಿ ಕೋಡ್

ಸಿ ++ ಕೋಡ್

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

int maxScore(string s) {
    int zero = 0, one = 0;
    for(int i=0;i<s.size();i++)
        (s[i] == '0') ? zero++ : one++;
    int curZero = (s[0] == '0'), curOne = (s[0] == '1');
    int ans = curZero + one - curOne;
    for(int i=1;i<s.size()-1;i++){
        (s[i] == '0') ? curZero++ : curOne++;
        ans = max(ans, curZero + one - curOne);
    }
    return ans;
}

int main(){
    cout<<maxScore("00111");
}
5

ಜಾವಾ ಕೋಡ್

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int maxScore(String s) {
        int one = 0, zero = 0;
        for(int i=0;i<s.length();i++)
            if(s.charAt(i) == '0')
                zero++;
            else
                one++;
        int curZero = (s.charAt(0) == '0' ? 1 : 0), curOne = (s.charAt(0) == '1' ? 1 : 0);
        int ans = curZero + one - curOne;
        for(int i=1;i<s.length()-1;i++){
            if(s.charAt(i) == '0')curZero++;
            else curOne++;
            ans = Math.max(ans, curZero + one-curOne);
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(maxScore("00111"));
  }
}
5

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ವಿಧಾನವು ಎರಡು-ಪಾಸ್ ಆಗಿದ್ದರೂ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಇನ್ನೂ ರೇಖೀಯವಾಗಿ ಉಳಿದಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ಏಕೆಂದರೆ ಅಲ್ಗಾರಿದಮ್‌ನಲ್ಲಿ ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಬಳಸಲಾಗುತ್ತದೆ.