స్ట్రింగ్ లీట్‌కోడ్ పరిష్కారాన్ని విభజించిన తర్వాత గరిష్ట స్కోరు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గూగుల్
స్ట్రింగ్

విభజన తరువాత గరిష్ట స్కోరు సమస్య 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), అల్గోరిథంలో స్థిరమైన స్థలం ఉపయోగించబడుతుంది.