લાંબી સાચી કૌંસ સબસેક્વન્સ માટે રેંજ ક્વેરીઝ


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન કોડનેશન Google પેપાલ ઉબેર
અરે સ્ટેક

તમને કેટલાક કૌંસ અનુગામીનો ક્રમ આપવામાં આવે છે, અન્ય શબ્દોમાં, તમને '(' અને ') જેવા કૌંસ આપવામાં આવે છે અને તમને પ્રારંભિક બિંદુ અને અંતિમ બિંદુ તરીકે ક્વેરી શ્રેણી આપવામાં આવે છે. સમસ્યા, “લાંબી સાચી કૌંસ સબસેક્વેન્સ માટે રેંજ ક્વેરીઝ” આપેલ ક્વેરી રેન્જની અંદર, (") () ("), "(())", "(" જેવા યોગ્ય કૌંસ સબક્વેન્સ અથવા સંતુલિત કૌંસ કૌંસની મહત્તમ લંબાઈ શોધવા માટે પૂછે છે. " (()) ”” વગેરે.

ઉદાહરણ

String s = “()())()(())( ”
startingPoint = 4
endingPoint = 8
2

સમજૂતી

ફક્ત સાચા કૌંસ અનુક્રમણિકા 5 અને 6 પર છે.

લાંબી સાચી કૌંસ સબસેક્વન્સ માટે રેંજ ક્વેરીઝ

 

અલ્ગોરિધમ

  1. ઘોષણા કરો એ સ્ટેક.
  2. સંપૂર્ણ પસાર શબ્દમાળા અને શરૂઆતના બધા કૌંસને સ્ટેકમાં દબાણ કરો.
    1. જો તે કૌંસ ખોલતું નથી, તો સ્ટેક ખાલી નથી કે નહીં તે તપાસો, પછી તે અનુક્રમણિકાને 1 તરીકે ચિહ્નિત કરો.
      1. સ્ટેકનું કદ મેળવો અને તે અનુક્રમણિકાને 1 પર ચિહ્નિત કરો અને સ્ટેકમાંથી ટોચનું તત્વ પ popપ કરો.
    2. જો સ્ટેક ખાલી છે, તો તે ઇન્ડેક્સને બંધ કૌંસ સાથે 0 તરીકે ચિહ્નિત કરો.
  3. શબ્દમાળાની લંબાઈ સુધી પસાર કરો અને નીચે આપેલા દરેક તત્વનો સરવાળો કરો.
    1. ક્લોઝડ બ્રેકેટ્સ [i] = ક્લોઝડ કૌંસ [i] + ક્લોઝબ્રેકેટ [i-1]
    2. ઓપનિંગ કૌંસ [i] = ઓપનિંગ કૌંસ [i] + ઓપનિંગ કૌંસ [i-1]
  4. ક્વેરીને પ્રારંભિક અને અંતિમ પોઇન્ટ તરીકે લો.
    1. ઓપનિંગ કૌંસ [પ્રારંભિક પોઇન્ટ -1] = ઉદઘાટન કૌંસ [પ્રારંભિક બિંદુ] તપાસો
      1. રીટર્ન (ક્લોઝબ્રેકેટ્સ [અંતિમ પોઇન્ટ] - ઓપનિંગ કૌંસ [પ્રારંભિક બિંદુ]) * 2.
    2. અન્ય વળતર (બંધ કરાયેલ કૌંસ [અંતિમ પોઇન્ટ] - ઓપનિંગ કૌંસ [પ્રારંભિક બિંદુ] + 1) * 2.

સમજૂતી

આપણને કૌંસના ક્રમની એક શબ્દમાળા આપવામાં આવી છે, જેમાં '(' અને ')' પ્રકારનો કૌંસ હાજર છે, અને શ્રેણીના ઘણા પ્રશ્નો આપવામાં આવે છે. ક્વેરીઝ પ્રારંભિક બિંદુ અને સબઅરેનના અંતિમ બિંદુના રૂપમાં આપવામાં આવે છે. અમને આપેલ શ્રેણીમાં, યોગ્ય અથવા સંતુલિત કૌંસની મહત્તમ લંબાઈ શોધવા માટે કહેવામાં આવે છે. સાચા અથવા સંતુલિત કૌંસને કૌંસ ખોલવા અથવા બંધ કરવા સમાન ગણવામાં આવે છે. પરંતુ અમને એક શ્રેણી આપવામાં આવી છે, આપણે કૌંસની સાચી પેટાક્વન્સી સાથે શક્ય તે મહત્તમ લંબાઈ શોધવી પડશે.

શોધવા માટે, ડેટા સ્ટ્રક્ચર જેવા સ્ટેક ફાયદાકારક રહેશે. અમે બધા ઉદઘાટન કૌંસને સ્ટેકમાં દબાણ કરવા જઈશું જેથી આપણે શોધી શકીએ કે જ્યાંથી આપણે પ્રારંભ કરવો પડશે. જો વર્તમાન કૌંસ એ ઉદઘાટન કૌંસ નથી. અમારે તપાસ કરવી પડશે કે આગળની કામગીરી કરવા માટે સ્ટેક ખાલી ન હોવો જોઇએ. અલબત્ત, તે બંધ કૌંસ હશે. જો તે ઉદઘાટન કૌંસ નથી, તો પછી આપણે તે બંધ કૌંસ અનુક્રમણિકાને 1 તરીકે ચિહ્નિત કરીએ છીએ. અને પછીના પગલામાં, આપણે સ્ટેકનું કદ મેળવીશું અને તે કદને અનુક્રમણિકા તરીકે ગણીશું અને તે અનુક્રમણિકાને 1 ની જેમ ચિહ્નિત કરીશું. ઓપનિંગ કૌંસ, અને સ્ટેકના તત્વને પ popપ કરો. શબ્દમાળાની લંબાઈ સુધી ટ્રાંસ્વર કરો અને દરેકના મૂલ્યનો સરવાળો કરો ઓપનિંગ કૌંસ અને ક્લોઝિંગબ્રેસ અને દરેક અનુક્રમણિકા પર સરવાળો.

ઇનપુટ તરીકે ક્વેરીઝ લો અને માં તપાસો ક્લોઝિંગબ્રેસ જો પ્રારંભિક બિંદુ મૂલ્ય અગાઉના મૂલ્યની બરાબર હોય ઓપનિંગ કૌંસ પછી ક્લોઝિંગબ્રેકેટ્સ [અંતિમ પોઇન્ટ] - ઓપનિંગ કૌંસ [પ્રારંભિક બિંદુ] ના તફાવતથી બે વાર નંબર પાછો. અન્યથા ક્લોઝિંગબ્રેકેટ્સ [અંતિમ પોઇન્ટ] ના તફાવતના બે વાર નંબર પાછા આપો - ઓપનિંગ કૌંસ [પ્રારંભિક બિંદુ] + ૧. અમને ઇચ્છિત જવાબ મળશે.

કોડ

સૌથી લાંબી સાચી કૌંસ સબસિક્વેન્સ માટેની શ્રેણી પ્રશ્નોના જવાબ માટે સી ++ કોડ

#include<iostream>
#include<cstring>
#include<stack>

using namespace std;

void correctBracketsLength(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], char* str, int n)
{
    stack<int> STACK;
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == '(')
            STACK.push(i);
        else
        {
            if (!STACK.empty())
            {
                CLOSEDBRACKETS[i] = 1;
                OPENINGBRACKETS[STACK.top()] = 1;
                STACK.pop();
            }
            else
                CLOSEDBRACKETS[i] = 0;
        }
    }
    for (int i = 1; i < n; i++)
    {
        CLOSEDBRACKETS[i] += CLOSEDBRACKETS[i - 1];
        OPENINGBRACKETS[i] += OPENINGBRACKETS[i - 1];
    }
}
int query(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], int startingPoint, int endingPoint)
{
    if (OPENINGBRACKETS[startingPoint - 1] == OPENINGBRACKETS[startingPoint])
    {
        return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint]) * 2;
    }
    else
    {
        return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint] + 1) * 2;
    }
}
int main()
{
    char str[] = "()())()(())(";
    int n = strlen(str);

    int CLOSEDBRACKETS[n + 1] = { 0 };
    int OPENINGBRACKETS[n + 1] = { 0 };

    correctBracketsLength(OPENINGBRACKETS, CLOSEDBRACKETS, str, n);

    int startingPoint = 4, endingPoint = 8;

    cout << "Maximum Length within "
         << startingPoint << " and " << endingPoint << " = "
         << query(OPENINGBRACKETS, CLOSEDBRACKETS, startingPoint, endingPoint) << endl;

    return 0;
}
Maximum Length within 4 and 8 = 2

સૌથી લાંબી સાચી કૌંસ સબસેક્વેન્સ માટેની રેંજ ક્વેરીઝનો જવાબ આપવા માટે જાવા કોડ

import java.util.*;

class LongestCorrectBracket
{
    public static void correctBracketsLength(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], String str, int n)
    {
        Stack<Integer> STACK = new Stack<>();;

        for(int i = 0; i < n; i++)
        {
            if (str.charAt(i) == '(')
                STACK.add(i);
            else
            {
                if (!STACK.isEmpty())
                {
                    CLOSEDBRACKETS[i] = 1;
                    OPENINGBRACKETS[STACK.peek()] = 1;
                    STACK.pop();
                }
                else
                    CLOSEDBRACKETS[i] = 0;
            }
        }
        for(int i = 1; i < n; i++)
        {
            CLOSEDBRACKETS[i] += CLOSEDBRACKETS[i - 1];
            OPENINGBRACKETS[i] += OPENINGBRACKETS[i - 1];
        }
    }
    static int query(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], int startingPoint, int endingPoint)
    {
        if (OPENINGBRACKETS[startingPoint - 1] == OPENINGBRACKETS[startingPoint])
        {
            return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint]) * 2;
        }
        else
        {
            return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint] + 1) * 2;
        }
    }
    public static void main(String[] args)
    {
        String str = "()())()(())(";
        int n = str.length();

        int CLOSEDBRACKETS[] = new int[n + 1];
        int OPENINGBRACKETS[] = new int[n + 1];

        correctBracketsLength(OPENINGBRACKETS, CLOSEDBRACKETS, str, n);

        int startingPoint = 4, endingPoint = 8;
        System.out.print("Maximum Length within " +
                         startingPoint + " and " + endingPoint +
                         " = " + query(OPENINGBRACKETS, CLOSEDBRACKETS, startingPoint,
                                       endingPoint) + "\n");
    }
}
Maximum Length within 4 and 8 = 2

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (1) દરેક ક્વેરી કરવા માટે. પરંતુ પૂર્વસત્તા જરૂરી છે ઓ (એન + ક્યૂ) સમય. આમ એલ્ગોરિધમની કુલ સમયની જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” શબ્દમાળા ની લંબાઈ છે. અમે શરૂઆતના કૌંસ સ્ટોર કરવા અને કૌંસની ગણતરી બંધ કરવા માટે બે એરે બનાવી છે. જગ્યાની જટિલતા રેખીય છે.