ਸਭ ਤੋਂ ਲੰਬੇ ਸਹੀ ਬਰੈਕਟ ਸਬਸਕੁਇੰਸ ਲਈ ਸੀਮਾ ਪ੍ਰਸ਼ਨ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਕੋਡਨੇਸ਼ਨ ਗੂਗਲ ਪੇਪਾਲ ਉਬੇਰ
ਅਰੇ ਸਟੈਕ

ਤੁਹਾਨੂੰ ਕੁਝ ਬਰੈਕਟ ਸਬਕੁਐਂਸ ਦਾ ਕ੍ਰਮ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ, ਦੂਜੇ ਸ਼ਬਦਾਂ ਵਿੱਚ, ਤੁਹਾਨੂੰ '(' ਅਤੇ ')' ਵਰਗੀਆਂ ਬਰੈਕਟ ਦਿੱਤੀਆਂ ਜਾਂਦੀਆਂ ਹਨ ਅਤੇ ਤੁਹਾਨੂੰ ਇੱਕ ਬਿੰਦੂ ਅਤੇ ਅੰਤ ਬਿੰਦੂ ਦੇ ਤੌਰ ਤੇ ਇੱਕ ਪ੍ਰਸ਼ਨ ਰੇਂਜ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ. ਸਮੱਸਿਆ “ਲੰਬੇ ਸਮੇਂ ਲਈ ਸਹੀ ਬ੍ਰੈਕਿਟ ਸਬਸਕੁਆਇੰਸ ਲਈ ਸੀਮਾ ਪ੍ਰਸ਼ਨ” ਕਿਸੇ ਖਾਸ ਪੁੱਛਗਿੱਛ ਵਿਚ “() () (“) ”,“ (()) ”,“ (ਜਿਵੇਂ ਕਿ ਸਹੀ ਬਰੈਕੇਟ ਸਬਕੈਂਸ ਜਾਂ ਸੰਤੁਲਿਤ ਬਰੈਕਟ ਬਰੈਕੇਟਸ ਦੀ ਅਧਿਕਤਮ ਲੰਬਾਈ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਪੁੱਛਦੀ ਹੈ। (()) ”ਆਦਿ।

ਉਦਾਹਰਨ

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

ਕਥਾ

ਸਿਰਫ ਸਹੀ ਬਰੈਕਟ ਇੰਡੈਕਸ 5 ਅਤੇ 6 ਤੇ ਹਨ.

ਸਭ ਤੋਂ ਲੰਬੇ ਸਹੀ ਬਰੈਕਟ ਸਬਸਕੁਇੰਸ ਲਈ ਸੀਮਾ ਪ੍ਰਸ਼ਨ

 

ਐਲਗੋਰਿਥਮ

  1. ਘੋਸ਼ਣਾ ਏ ਸਟੈਕ.
  2. ਪੂਰਾ ਪਾਰ ਕਰੋ ਸਤਰ ਅਤੇ ਸਾਰੇ ਉਦਘਾਟਨ ਬਰੈਕਟਾਂ ਨੂੰ ਸਟੈਕ ਵਿੱਚ ਧੱਕੋ.
    1. ਜੇ ਇਹ ਬਰੈਕਟ ਨਹੀਂ ਖੋਲ੍ਹ ਰਿਹਾ ਤਾਂ ਜਾਂਚ ਕਰੋ ਕਿ ਸਟੈਕ ਖਾਲੀ ਨਹੀਂ ਹੈ, ਫਿਰ ਉਸ ਸੂਚੀ ਨੂੰ 1 ਦੇ ਤੌਰ ਤੇ ਚਿੰਨ੍ਹਿਤ ਕਰੋ.
      1. ਸਟੈਕ ਦਾ ਆਕਾਰ ਪ੍ਰਾਪਤ ਕਰੋ ਅਤੇ ਉਸ ਸੂਚੀ ਨੂੰ 1 ਤੇ ਨਿਸ਼ਾਨ ਲਗਾਓ, ਅਤੇ ਸਟੈਕ ਤੋਂ ਚੋਟੀ ਦੇ ਤੱਤ ਨੂੰ ਪੌਪ ਕਰੋ.
    2. ਜੇ ਸਟੈਕ ਖਾਲੀ ਹੈ ਤਾਂ ਉਸ ਇੰਡੈਕਸ ਨੂੰ ਬਰੈਕਟ ਨਾਲ ਬੰਦ ਕਰਕੇ 0 ਦੇ ਤੌਰ ਤੇ ਮਾਰਕ ਕਰੋ.
  3. ਸਤਰ ਦੀ ਲੰਬਾਈ ਤੱਕ ਦਾ ਰਾਹ ਲਓ ਅਤੇ ਹੇਠ ਦਿੱਤੇ ਅਨੁਸਾਰ ਹਰੇਕ ਤੱਤ ਦਾ ਜੋੜ ਕਰੋ.
    1. ਕਲੋਜ਼ਡ ਬਰੈਕੇਟਸ [i] = ਕਲੋਜ਼ਡ ਬਰੈਕੇਟਸ [i] + ਕਲੋਜ਼ਡ ਬਰੈਕੇਟਸ [i-1]
    2. ਓਪਨਿੰਗ ਬਰੈਕਟਸ [i] = ਓਪਨਿੰਗ ਬਰੈਕੇਟਸ [i] + ਓਪਨਿੰਗ ਬਰੈਕਟਸ [i-1]
  4. ਪੁੱਛਗਿੱਛ ਨੂੰ ਸ਼ੁਰੂਆਤੀ ਬਿੰਦੂ ਅਤੇ ਅੰਤਮ ਪੁਆਇੰਟ ਦੇ ਤੌਰ ਤੇ ਲਓ.
    1. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਓਪਨਿੰਗ ਬਰੈਕੇਟਸ [ਸ਼ੁਰੂਆਤੀ ਪੁਆਇੰਟ -1] = ਓਪਨਿੰਗ ਬਰੈਕਟ [ਸ਼ੁਰੂਆਤੀ ਬਿੰਦੂ]
      1. ਵਾਪਸੀ (ਬੰਦ ਕੀਤੀਆ ਬਰੈਕਟਸ [ਅੰਤ ਵਾਲੀ ਪੁਆਇੰਟ] - ਖੁੱਲ੍ਹਣ ਵਾਲੀਆਂ ਬਰੈਕਟ [ਸ਼ੁਰੂਆਤੀ ਬਿੰਦੂ]) * 2.
    2. ਹੋਰ ਵਾਪਸੀ (ਬੰਦ ਕੀਤੀਆ ਬਰੈਕਟਸ [ਅੰਤ ਵਾਲੀ ਪੁਆਇੰਟ] - ਖੁੱਲ੍ਹਣ ਵਾਲੀਆਂ ਬ੍ਰੈਕਟਾਂ [ਅਰੰਭਕ ਪੁਆਇੰਟ] + 1) * 2.

ਕਥਾ

ਸਾਨੂੰ ਬਰੈਕਟਸ ਦੇ ਕ੍ਰਮ ਦੀ ਇਕ ਸਤਰ ਦਿੱਤੀ ਗਈ ਹੈ, ਜਿਸ ਵਿਚ '(' ਅਤੇ ')' ਕਿਸਮ ਦੀ ਬਰੈਕਟ ਮੌਜੂਦ ਹੈ, ਅਤੇ ਬਹੁਤ ਸਾਰੇ ਪ੍ਰਸ਼ਨ ਦਿੱਤੇ ਗਏ ਹਨ. ਪ੍ਰਸ਼ਨਾਂ ਨੂੰ ਸ਼ੁਰੂਆਤੀ ਬਿੰਦੂ ਅਤੇ ਸੁਬਰੇਰੀ ਦੇ ਅੰਤ ਵਾਲੇ ਬਿੰਦੂ ਦੇ ਰੂਪ ਵਿੱਚ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ. ਸਾਨੂੰ ਦਿੱਤੀ ਗਈ ਸੀਮਾ ਦੇ ਅੰਦਰ, ਸਹੀ ਜਾਂ ਸੰਤੁਲਿਤ ਬਰੈਕਟ ਦੀ ਅਧਿਕਤਮ ਲੰਬਾਈ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਕਿਹਾ ਜਾਂਦਾ ਹੈ. ਸਹੀ ਜਾਂ ਸੰਤੁਲਿਤ ਬਰੈਕਟ ਬਰੈਕਟ ਨੂੰ ਖੋਲ੍ਹਣ ਜਾਂ ਬੰਦ ਕਰਨ ਦੇ ਬਰਾਬਰ ਨੰਬਰ ਦੇ ਤੌਰ ਤੇ ਮੰਨਿਆ ਜਾ ਸਕਦਾ ਹੈ. ਪਰ ਸਾਨੂੰ ਇੱਕ ਸੀਮਾ ਦਿੱਤੀ ਗਈ ਹੈ, ਸਾਨੂੰ ਵੱਧ ਤੋਂ ਵੱਧ ਲੰਬਾਈ ਲੱਭਣੀ ਪਏਗੀ ਜੋ ਕਿ ਬਰੈਕਟ ਦੇ ਸਹੀ ਉਪਸਕ੍ਰਿਤੀ ਦੇ ਨਾਲ ਸੰਭਵ ਹੈ.

ਇਹ ਪਤਾ ਲਗਾਉਣ ਲਈ, ਸਟੈਕ ਜਿਵੇਂ ਡੇਟਾ likeਾਂਚਾ ਲਾਭਦਾਇਕ ਹੋਵੇਗਾ. ਅਸੀਂ ਸਾਰੇ ਉਦਘਾਟਨ ਬਰੈਕਟਾਂ ਨੂੰ ਸਟੈਕ ਵਿੱਚ ਧੱਕਣ ਜਾ ਰਹੇ ਹਾਂ ਤਾਂ ਜੋ ਸਾਨੂੰ ਪਤਾ ਲੱਗ ਸਕੇ ਕਿ ਸਾਨੂੰ ਕਿੱਥੋਂ ਸ਼ੁਰੂ ਕਰਨਾ ਹੈ. ਜੇ ਮੌਜੂਦਾ ਬਰੈਕਟ ਖੁੱਲ੍ਹਣ ਵਾਲੀ ਬਰੈਕਟ ਨਹੀਂ ਹੈ. ਸਾਨੂੰ ਜਾਂਚ ਕਰਨੀ ਪਏਗੀ ਕਿ ਕੀ ਅਗਲੇ ਕਾਰਜਾਂ ਲਈ ਸਟੈਕ ਖਾਲੀ ਨਹੀਂ ਹੋਣਾ ਚਾਹੀਦਾ. ਬੇਸ਼ਕ, ਇਹ ਇੱਕ ਬੰਦ ਕਰਨ ਵਾਲੀ ਬਰੈਕਟ ਹੋਵੇਗੀ. ਜੇ ਇਹ ਖੁੱਲ੍ਹਣ ਵਾਲਾ ਬਰੈਕਟ ਨਹੀਂ ਹੈ, ਤਾਂ ਅਸੀਂ ਉਸ ਬਰੈਕਟ ਇੰਡੈਕਸ ਨੂੰ 1 ਦੇ ਤੌਰ ਤੇ ਨਿਸ਼ਾਨ ਲਗਾਉਂਦੇ ਹਾਂ. ਅਤੇ ਅਗਲੇ ਕਦਮ ਵਿੱਚ, ਅਸੀਂ ਸਟੈਕ ਦਾ ਆਕਾਰ ਪ੍ਰਾਪਤ ਕਰਾਂਗੇ ਅਤੇ ਉਸ ਅਕਾਰ ਨੂੰ ਇੱਕ ਸੂਚਕਾਂਕ ਮੰਨਾਂਗੇ ਅਤੇ ਉਸ ਸੂਚਕਾਂਕ ਨੂੰ 1 ਦੇ ਰੂਪ ਵਿੱਚ ਨਿਸ਼ਾਨ ਲਗਾਵਾਂਗੇ. ਓਪਨਿੰਗ ਬਰੈਕਟ, ਅਤੇ ਸਟੈਕ ਦੇ ਤੱਤ ਨੂੰ ਪੌਪ ਕਰੋ. ਸਤਰ ਦੀ ਲੰਬਾਈ ਤਕ ਟਰਾਂਸਫਰ ਕਰੋ, ਅਤੇ ਹਰੇਕ ਦੇ ਮੁੱਲ ਦਾ ਜੋੜ ਦਿਓ ਓਪਨਿੰਗ ਬਰੈਕਟ ਅਤੇ ਸਮਾਪਤੀ ਅਤੇ ਹਰੇਕ ਇੰਡੈਕਸ ਤੇ ਜੋੜ ਕੇ ਰੱਖੋ.

ਪ੍ਰਸ਼ਨਾਂ ਨੂੰ ਇਨਪੁਟ ਦੇ ਤੌਰ ਤੇ ਲਓ, ਅਤੇ ਵਿੱਚ ਜਾਂਚ ਕਰੋ ਸਮਾਪਤੀ ਜੇ ਸ਼ੁਰੂਆਤੀ ਬਿੰਦੂ ਦਾ ਮੁੱਲ ਪਿਛਲੇ ਮੁੱਲ ਦੇ ਬਰਾਬਰ ਹੈ ਓਪਨਿੰਗ ਬਰੈਕਟ ਫਿਰ ਕਲੋਜ਼ਿੰਗਬ੍ਰੇਕਸ [ਐਂਡਿੰਗਪੁਆਇੰਟ] - ਓਪਨਿੰਗ ਬਰੈਕੇਟਸ [ਅਰੰਭਕ ਪੁਆਇੰਟ] ਦੇ ਅੰਤਰ ਦੇ ਦੁਗਣੇ ਨੰਬਰ ਨੂੰ ਵਾਪਸ ਕਰੋ. ਦੂਸਰੇ ਨੰਬਰ ਨੂੰ ਬੰਦ ਕਰਨ ਵਾਲੀਆਂ ਬਰੈਕਟਾਂ [ਐਂਡਿੰਗਪੁਆਇੰਟ] ਦੇ ਅੰਤਰ ਦੇ ਦੋ ਵਾਰ ਵਾਪਸ ਕਰੋ - ਖੁੱਲ੍ਹਣ ਵਾਲੀਆਂ ਬ੍ਰੈਕਟਾਂ [ਸ਼ੁਰੂਆਤੀ ਬਿੰਦੂ] + 1. ਸਾਨੂੰ ਲੋੜੀਂਦਾ ਜਵਾਬ ਮਿਲੇਗਾ.

ਕੋਡ

ਸਭ ਤੋਂ ਲੰਬੇ ਸਹੀ ਬਰੈਕਟ ਸਬਸਕਸੇਂਸ ਲਈ ਸੀਮਾ ਪ੍ਰਸ਼ਨਾਂ ਦੇ ਜਵਾਬ ਲਈ ਸੀ ++ ਕੋਡ

#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) ਜਿੱਥੇ ਕਿ “ਐਨ” ਸਤਰ ਦੀ ਲੰਬਾਈ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਉਦਘਾਟਨੀ ਬਰੈਕਟ ਅਤੇ ਸਟੋਰਿੰਗ ਬਰੈਕਟ ਗਿਣਤੀ ਲਈ ਦੋ ਐਰੇ ਬਣਾਏ ਹਨ. ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਲੀਨੀਅਰ ਹੈ.