Konwertuj ciąg, który jest powtórzeniem podłańcucha o długości K.

Poziom trudności Średni
Często zadawane pytania Accenture Adobe American Express Pamięci danych FreeCharge
Haszysz Hashing HashMap sznurodwiedzajacy 258

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W zadaniu „Konwersja łańcucha, który jest powtórzeniem podłańcucha o długości K”, podaliśmy ciąg „S” i liczba całkowita „k”. Napisz program, który sprawdzi, czy jest możliwe przekonwertowanie go na łańcuch będący powtórzeniem podłańcucha o k znakach.

Format wejściowy

Pierwsza linia zawierająca ciąg „s”.

Drugi wiersz zawierający liczbę całkowitą „k”.

Format wyjściowy

Wypisz „TAK”, jeśli jest możliwe przekonwertowanie go na łańcuch będący powtórzeniem podłańcucha o k znakach. W przeciwnym razie wydrukuj „NIE”.

ograniczenia

  • 1 <= | s | <= 10 ^ 6
  • s [i] musi być małym alfabetem angielskim

Przykład

abcdefabc
3
YES

Wyjaśnienie: Tutaj możemy zamienić „def” na „abc”. Nasz zaktualizowany ciąg to „abcabcabc”. Teraz możemy łatwo sprawdzić, czy połączymy abc trzy razy, a następnie otrzymamy ten ciąg.

acdaacda
2
NO

Wyjaśnienie: Nie ma podciągu o długości 2, który możemy zastąpić i uformować ciąg w taki sposób, że otrzymamy go przez konkatenację podciągu o długości k.

Algorytm

1. Przejdź przez łańcuch i zbuduj mapę zawierającą częstotliwość podciągów (od 0 do k-1, od k do 2k-1, od 2k do 3k-1 itd.) O długości k.maps ciągów o długości k.

2. Jeśli istnieją tylko dwa różne podciągi o długości k, a liczba jednego z podciągów wynosi 1, wypisz „TAK”.

3. W przeciwnym razie wydrukuj „NIE”.

Realizacja

Program w C ++ do konwersji ciągu będącego powtórzeniem podłańcucha o długości K.

#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; 
}

Program w języku Java do konwersji ciągu będącego powtórzeniem podłańcucha o długości K.

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

Analiza złożoności w celu przekształcenia łańcucha będącego powtórzeniem podłańcucha o długości K.

Złożoność czasowa

Na) gdzie n jest rozmiarem danego ciągu „s”. Tutaj po prostu tworzymy podciąg (od 0 do k-1, od k do 2k-1, od 2k do 3k-1 itd.) Ok k długości i zliczamy ich częstotliwość za pomocą mapy skrótów. Tutaj robimy to w czasie liniowym.

Złożoność przestrzeni

Na) gdzie n jest rozmiarem danego ciągu „s”. Tutaj używamy mapy skrótów do przechowywania liczby podciągów o długości k.

Wywiady dotyczące projektowania systemu pękania
Translate »