길이가 K 인 부분 문자열의 반복 인 문자열 변환

난이도 중급
자주 묻는 질문 Accenture 어도비 벽돌 아메리칸 익스프레스 데이터 브릭 무료
해시 해싱 해시맵 조회수 258

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

문제 정책

"길이 K의 부분 문자열의 반복 인 문자열 변환"문제에서 우리는 "s"및 정수 "k". k 개의 문자가있는 부분 문자열의 반복 인 문자열로 변환 할 수 있는지 확인하는 프로그램을 작성하십시오.

입력 형식

문자열 "s"를 포함하는 첫 번째 줄입니다.

정수 값 "k"를 포함하는 두 번째 줄입니다.

출력 형식

k 문자가있는 부분 문자열의 반복 인 문자열로 변환 할 수 있으면 "YES"를 인쇄하십시오. 그렇지 않으면“NO”를 인쇄하십시오.

제약

  • 1 <= | s | <= 10 ^ 6
  • s [i]는 소문자 영어 알파벳이어야합니다.

abcdefabc
3
YES

설명 : 여기서 "def"를 "abc"로 바꿀 수 있습니다. 그러면 업데이트 된 문자열 s는 "abcabcabc"입니다. 이제 abc를 세 번 연결하면이 문자열을 쉽게 얻을 수 있습니다.

acdaacda
2
NO

설명 : 길이가 2 인 부분 문자열은 없습니다. 우리는 길이 k의 부분 문자열을 연결하여 얻을 수 있도록 문자열을 바꾸고 형성 할 수 있습니다.

암호알고리즘

1. 문자열을 가로 질러 길이 k의 하위 문자열 (0에서 k-1, k에서 2k-1, 2k에서 3k-1 등)의 빈도를 포함하는 맵을 작성합니다. 길이 k의 문자열을 매핑합니다.

2. 길이가 k 인 두 개의 다른 부분 문자열 만 있고 부분 문자열 중 하나의 개수가 1이면“YES”를 인쇄합니다.

3. 그렇지 않으면“NO”를 인쇄하십시오.

실시

길이 K의 부분 문자열이 반복되는 문자열을 변환하는 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    string s;
    cin>>s;
    int k;
    cin>>k;
    int n=s.length();
    if(n%k!=0)
    {
        cout<<"NO"<<endl;
    }
    else
    {
        unordered_map<string, int> m; 
        for (int i=0; i<n; i+=k) 
        {
            m[s.substr(i, k)]++;
        }
        if(m.size()==1)
        {
            cout<<"YES"<<endl;
        }
        else if(m.size()==2)
        {
            if(m.begin()->second==1 || m.begin()->second==(n/k-1))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0; 
}

길이 K의 하위 문자열이 반복되는 문자열을 변환하는 Java 프로그램

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int k = sr.nextInt();
                int n=s.length();
                if(n%k!=0)
                {
                    System.out.println("NO");
                }
                else
                {
                    HashMap<String, Integer> m = new HashMap<>();
                    for(int i=0;i<n;i+=k)
                    {
                        String x = s.substring(i,i+k);
                        int temp = m.get(s.substring(i,i+k))==null? 0 : m.get(s.substring(i,i+k));
                        m.put(s.substring(i,i+k), temp+1);
                    }
                    if(m.size()==1)
                    {
                        System.out.println("YES");
                    }
                    else if(m.size()==2)
                    {
                        int flag=0;
                        for(Map.Entry<String, Integer> e : m.entrySet())
                        {
                            if(e.getValue()==1)
                            {
                                flag=1;
                                break;
                            }
                        }
                        if(flag==0)
                        {
                            System.out.println("NO");
                        }
                        else
                        {
                            System.out.println("YES");
                        }
                    }
                    else
                    {
                        System.out.println("NO");
                    }
                }
  } 
} 
abcdabab
YES

길이가 K 인 부분 문자열이 반복되는 문자열을 변환하기위한 복잡성 분석

시간 복잡성

O (N) 어디에 n 주어진 문자열 "s"의 크기입니다. 여기서 우리는 간단히 substring (0에서 k-1, k에서 2k-1, 2k에서 3k-1 등) ok k 길이를 만들고 해시 맵을 사용하여 빈도를 계산합니다. 여기서 우리는 선형 시간으로 이것을합니다.

공간 복잡성

O (N) 어디에 n 주어진 문자열 "s"의 크기입니다. 여기서 우리는 길이가 k 인 부분 문자열의 개수를 저장하기 위해 해시 맵을 사용합니다.

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