유효한 가장 긴 부분 문자열의 길이

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 이베이 Facebook 구글 Microsoft 신탁 동네 짱 VM웨어 Yahoo
조회수 417

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“Length of Longest valid Substring”에서 우리는 여는 괄호와 닫는 괄호 만 포함합니다. 가장 오래 유효한 프로그램을 작성하십시오. 괄호 부분 문자열.

입력 형식

문자열 s를 포함하는 첫 번째 및 유일한 행.

출력 형식

가장 긴 유효한 괄호 하위 문자열의 길이를 나타내는 정수 n을 포함하는 첫 번째 및 유일한 행입니다.

제약

  • 1 <= | s | <= 10 ^ 5
  • s [i]는 '('또는 ')'여야합니다.

(())())
6

설명 :  "(()) ()"는 위에 주어진 문자열에서 가장 긴 유효한 괄호 하위 문자열입니다. 그래서 우리의 답은 6입니다.

유효한 가장 긴 부분 문자열의 길이에 대한 알고리즘

1. 빈 스택을 만들고 여기에 -1을 푸시합니다. -1은 다음 유효한 문자열에 대한 기본 케이스를 제공하는 것입니다.

2. 출력을 저장할 변수 'res'생성

3. 모든 문자를 처음부터 끝까지 순회

        a. 문자가 '('이면 현재 인덱스를 스택으로 푸시합니다.
        b. 그밖에,

  • 스택에서 요소를 팝합니다.
  • 스택이 비어 있지 않은 경우 현재 인덱스와 스택 맨 위의 차이를 사용하여 현재 유효한 하위 문자열의 길이를 찾습니다. 현재 길이가 결과보다 긴지 확인한 다음 결과를 업데이트하십시오.
  • 스택이 비어 있으면 현재 인덱스를 다음 유효한 하위 문자열의 기준으로 푸시합니다.

4. 'res'반환

알고리즘 구현-

s =“(())”
-1을 스택에 넣고 res = 0을 초기화합니다.

i = 0, s [0] = '(', 0을 스택으로 푸시, 이제 스택 = [-1,0]
i = 1, s [1] = '(', 1을 스택으로 푸시, 이제 스택 = [-1,0,1]
i = 2, s [2] = ')', pop ()이므로 이제 스택 = [-1,0]
res = max (res, i – stack.top ()) = max (0, 2-0) = max (0,2) = 2
i = 3, s [3] = ')', pop () 이제 스택 = [-1]
res = max (res, i – stack.top ()) = max (2, 3-(-1)) = max (2,4) = 4

따라서 가장 긴 길이는 = res = 4입니다.

실시

유효한 가장 긴 부분 문자열의 길이에 대한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
 
int maxLength(string s)
{
    int n = s.length();
 
    // Create a stack and push -1 as initial index to it.
    stack<int> stck;
    stck.push(-1);
 
    // Initialize res
    int res = 0;
 
    // Traverse all characters of given string
    for (int i=0; i<n; i++)
    {
        // If opening bracket, push index of it
        if (s[i] == '(')
          stck.push(i);
 
        else // If closing bracket, i.e.,s[i] = ')'
        {
            // Pop the previous opening bracket's index
            stck.pop();
 
            // Check if this length formed with base of
            // current valid substring is more than max 
            // so far
            if (!stck.empty())
                res = max(res, i - stck.top());
 
            // If stack is empty. push current index as 
            // base for next valid substring (if any)
            else stck.push(i);
        }
    }
 
    return res;
}
 
int main()
{
    string s;
    cin>>s;
    cout<<maxLength(s)<<endl;
    return 0;
}

가장 긴 유효한 하위 문자열 길이를위한 Java 프로그램

import static java.lang.Math.max;
import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static int maxLength(String s)
    {
        int n = s.length();

        // Create a stack and push -1 as initial index to it.
        Stack<Integer> stck = new Stack<Integer>();
        stck.push(-1);
        // Initialize res
        int res = 0;
        // Traverse all characters of given string
        for (int i=0; i<n; i++)
        {
            // If opening bracket, push index of it
            if(s.charAt(i) == '(')
              stck.push(i);

            else // If closing bracket, i.e.,s[i] = ')'
            {
                // Pop the previous opening bracket's index
                stck.pop();

                // Check if this length formed with base of
                // current valid substring is more than max 
                // so far
                if(stck.size()>0)
                    res = max(res, i - (Integer) stck.peek());
                // If stack is empty. push current index as 
                // base for next valid substring (if any)
                else stck.push(i);
            }
        }
        return res;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        System.out.println(maxLength(s));
    }
}
(()())((
6

가장 긴 유효 부분 문자열의 길이에 대한 복잡성 분석

시간 복잡성

O (N) 어디에 n 주어진 문자열의 크기입니다. 여기서 우리는 char 단위로 string char을 탐색하고 일정한 시간에 몇 가지 작업을 수행합니다.

공간 복잡성

O (N) 스택을 사용하기 때문입니다. 여기서 스택의 최대 크기는 n입니다.

균열 시스템 설계 인터뷰
Translate »