קייט פֿראגן פֿאַר לאָנגעסט קאָררעקט בראַקעט סאַבסאַקוואַנס


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַמאַזאָן קאָדנאַטיאָן גוגל פּייַפּאַל ובער
מענגע אָנלייגן

איר באַקומען אַ סיקוואַנס פון עטלעכע בראַקאַץ סאַבסאַקוואַנס, אין אנדערע ווערטער, איר באַקומען בראַקאַץ ווי '(' און ')' און איר באַקומען אַ אָנפֿרעג קייט ווי אַ סטאַרטינג פונט און סאָף פונט. די פּראָבלעם "ראַנגע פֿראגן פֿאַר לאָנגעסט קאָררעקט בראַקעט סאַבסאַקוואַנס" פרעגט צו געפֿינען די מאַקסימום לענג פון די ריכטיק קלאַמער סאַבסאַקוואַנס אָדער באַלאַנסט קלאַמער בראַקאַץ, אין אַ געגעבן אָנפֿרעג, ווי "() ()", "(())", "( (())) ”וכו’.

בייַשפּיל

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

דערקלערונג

די בלויז ריכטיק בראַקאַץ זענען אין אינדעקס 5 און 6.

קייט פֿראגן פֿאַר לאָנגעסט קאָררעקט בראַקעט סאַבסאַקוואַנס

 

אַלגאָריטהם

  1. דערקלערן א אָנלייגן.
  2. אַריבער די גאַנץ שטריקל און שטופּן אַלע עפן בראַקאַץ אין די אָנלייגן.
    1. אויב עס איז נישט עפן קלאַמער, קאָנטראָלירן אויב דער אָנלייגן איז נישט ליידיק און צייכן דעם אינדעקס ווי 1.
      1. באַקומען די גרייס פון דעם אָנלייגן און צייכן דעם אינדעקס צו 1 און קנאַל די שפּיץ עלעמענט פֿון די אָנלייגן.
    2. אויב די אָנלייגן איז ליידיק, צייכן די אינדעקס מיט קלאָוזד קאַנטיקער ווי 0.
  3. דורכגיין די לענג פון די שטריקל און סומע יעדער פון די עלעמענטן ווי ווייַטערדיק.
    1. closedBrackets [i] = closedBrackets [i] + closedBrackets [i-1]
    2. openingBrackets [i] = openingBrackets [i] + openingBrackets [i-1]
  4. נעמען די אָנפֿרעג ווי סטאַרטינגפּאָינט און סאָףפּאָינט.
    1. קוק אויב עפן בראַקאַץ [סטאַרטינגפּאָינט -1] = עפן בראַקאַץ [סטאַרטינגפּאָינט]
      1. ווייַזן (closedBrackets [endingPoint] - openingBrackets [startPoint]] * 2.
    2. אַנדערש צוריקקומען (closedBrackets [endingPoint] - openingBrackets [startpoint] + 1) * 2.

דערקלערונג

מיר באַקומען אַ שטריקל פון בראַקאַץ אין וואָס '(' און ')' טיפּ פון קלאַמערן זענען פאָרשטעלן און אַ נומער פון פֿראגן זענען געגעבן. פֿראגן זענען געגעבן אין די פאָרעם פון אַ סטאַרטינג פונט און אַ סאָף פונט פון די סובאַרראַי. מיר ווערן געבעטן צו געפֿינען אויס די מאַקסימום לענג פון ריכטיק אָדער באַלאַנסט קלאַמערן, אין די געגעבן קייט. ריכטיק אָדער באַלאַנסט בראַקאַץ קענען זיין קאַנסידערד ווי די גלייך ניט פון עפן אָדער קלאָוזינג בראַקאַץ. אָבער מיר האָבן אַ קייט, מיר דאַרפֿן צו געפֿינען די מאַקסימום לענג וואָס איז מעגלעך מיט אַ ריכטיק סאַבסטאַנסאַז פון בראַקאַץ.

אין סדר צו געפינען אויס, סטאַק ווי דאַטן סטרוקטור איז נוציק. מיר וועלן שטופּן אַלע עפן בראַקאַץ אין דעם אָנלייגן, אַזוי אַז מיר קענען געפֿינען פֿון וואָס מיר האָבן צו אָנהייבן. אויב די קראַנט קאַנטיקער איז נישט אַן עפן קאַנטיקער. מיר האָבן צו קאָנטראָלירן צי דער אָנלייגן זאָל ניט זיין ליידיק פֿאַר ווייַטער אַפּעריישאַנז. דאָך עס וועט זיין אַ קלאָוזינג קלאַמער. אויב עס איז נישט אַן עפן קלאַמער, מיר צייכן די קלאָוזינג קלאַמערן אינדעקס ווי 1. און אין דער ווייַטער שריט, מיר וועלן באַקומען די גרייס פון דעם אָנלייגן און מייַכל דעם גרייס ווי אַן אינדעקס און צייכן דעם אינדעקס ווי 1 פון בראַקאַץ, און קנאַל די עלעמענט פון דער אָנלייגן. אַריבער די לענג פון די שטריקל, און סומע יעדער ווערט פון די שטריקל openingBrackets און קלאָוזינגבראַקקעץ און קראָם די סומע ביי יעדער אינדעקס.

נעמען די פֿראגן ווי אַרייַנשרייַב, און טשעק אין די קלאָוזינגבראַקקעץ אויב די סטאַרטינג פונט ווערט איז גלייַך צו די פריערדיקע ווערט פון openingBrackets דערנאָך צוריקקומען די נומער ווי צוויי מאָל פון די חילוק פון קלאָוזינג בראַקקעץ [סאָףפּאָינט] - עפן בראַקקעץ [סטאַרטינגפּאָינט]. אַנדערש די נומער איז צוויי מאָל אַנדערש פון קלאָוזינג בראַקקעץ [סאָףפּאָינט] - עפן בראַקאַץ [סטאַרטינגפּאָינט] + 1. מיר וועלן באַקומען די געבעטן ענטפער.

קאָדעקס

C ++ קאָד צו ענטפֿערן קייט קוויריז פֿאַר לאָנגעסט קאָררעקט בראַקעט סאַבסאַקוואַנס

#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) פֿאַר יעדער אָנפֿרעג. אבער די פּרעקאָמפּוטאַטיאָן ריקווייערז אָ (n + q) צייַט. אזוי די גאַנץ צייט קאַמפּלעקסיטי פון די אַלגערידאַם איז לינעאַר.

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די לענג פון די שטריקל. זינט מיר באשאפן צוויי ערייז פֿאַר סטאָרידזש די עפן קלאַמער און קלאָוזינג קלאַמער ציילן. די פּלאַץ קאַמפּלעקסיטי איז לינעאַר.