Başqa bir sətirin bütün simvollarını ehtiva edən sətirdəki ən kiçik pəncərə

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Verilmiş sözün bütün simvollarını ehtiva edən verilmiş sətirdə ən qısa alt sətri tapın və ya digər sətirin bütün simvollarını ehtiva edən sətirdə ən kiçik pəncərəni tapın

İki s və t sətri verildikdə, s-də bütün simvolları ehtiva edən minimum pəncərəni tapacaq bir funksiya yazın

Məsələn 1

INPUT
S = “dərs fincanı”
T = "oti"

ÇIXDI
Minimum pəncərə “tori” dir

Məsələn 2

INPUT
S = "zaaskzaa"
T = "zsk"

ÇIXDI
Minimum pəncərə “skz” dir

Metod 1 (Gücün Gücü)

1. S dizəsinin bütün alt simlərini yaradın

2. S hər alt sətri üçün alt sətrin bütün T simvollarını içərisində olub olmadığını yoxlayın

3. T simli bütün simvolları birləşdirən ən kiçik uzunluqlu altlığı çap edin

Metod 2 (Səmərəli)

Zaman Mürəkkəbliyi: O (n)

Alqoritm

1. S sətrinin uzunluğu T sətrindən azdırsa, “NO pəncərə mövcud deyil” yazdırın. Başqa,

2. T sətrinin bir sayma T_count [] qurun
yəni, məsələn 2
z sayı 1, beləliklə T_count ['z'] = 1
s sayı 1-dir, buna görə T_count ['s'] = 1
k sayı 1-dir, buna görə T_count ['k'] = 1

3. Keçərkən S simli keçin

   a. S simli simvolların baş vermə sayını
yəni S_count ['z'] = 1, S cərgəsinin ilk simvolunda olduğumuz zaman
S_count ['a'] = 1, S cərgəsinin ikinci simvolunda olduğumuz zaman

    b. Əgər S sətri T sətri ilə uyğun gəlirsə, say dəyişənini artırın
yəni, məsələn 2
Əvvəlcə S cərgəsində char, z 'z', T sətrində də bir 'z' var, buna görə say sayını artırın, say = 1.

    c. Əgər sayım T simli uzunluğu ilə eynidirsə, onda pəncərəni tapdıq
yəni, məsələn 2
Sətrdə char 'k' olduqda S sayı 3 olur (T sətrin uzunluğu ilə eynidir). Buna görə pəncərəni tapdıq, yəni xarakterdən başlayaraq indiyə kimi “zaask”

  d. Pəncərəni tapdıqdan sonra cari pəncərənin əvvəlindən əlavə simvollar silməklə onu minimuma endirməyə çalışın
yəni, məsələn 2
Sətrdə char 'z' ikinci meydana çıxdıqdan sonra, yəni S_count ['z'] 1-dən dəyişir

2. Hansı ki, T_count ['z'] -dən böyükdür. Pəncərədə lazım olduğundan daha çox 'z' var deməkdir ki, əvvəlcə 'z' və digər yararsız simvolları başlanğıcdan çıxarın. yəni, indi pəncərə “skz” olur

e. pəncərənin başlanğıc və minimum uzunluğunu yeniləyin, yəni 'z' dən 's' və min_length dəyişikliklərini 5 ilə 3 arasında dəyişin

f. Minimum uzunluq pəncərəsini çap edin

C ++ Proqramı

#include<bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;
  
// Function to find smallest window containing
// all characters of T
string findSubString(string S, string T)
{
    int Slen = S.length();
    int Tlen = T.length();
 
    // check if string's length is less than T's
    // length. If yes then no such window can exist
    if (Slen < Tlen)
    {
        cout << "No such window exists";
        return "";
    }
 
    int S_count[NO_OF_CHARS] = {0};
    int T_count[NO_OF_CHARS] = {0};
 
    // store occurrence of characters of 't'
    for (int i = 0; i < Tlen; i++)
        T_count[T[i]]++;
 
    int start = 0, start_index = -1, min_len = INT_MAX;
 
    // start traversing the string
    int count = 0;  // count of characters
    for (int i = 0; i < Slen ; i++)
    {
        // count occurrence of characters of string
        S_count[S[i]]++;
 
        // If s's char matches with t's char
        // then increment count
        if (T_count[S[i]] != 0 &&
            S_count[S[i]] <= T_count[S[i]] )
            count++;
 
        // if all the characters are matched
        if (count == Tlen)
        {
            //minimizng the current window
            //If the current window has a character which occured more number of times
            //than the character in T string, then remove starting chars
            while ( S_count[S[start]] > T_count[S[start]]
                   || T_count[S[start]] == 0)
            {
 
                if (S_count[S[start]] > T_count[S[start]])
                    S_count[S[start]]--;
                start++;
            }
 
            // update window size
            int len_window = i - start + 1;
            if (min_len > len_window)
            {
                min_len = len_window;
                start_index = start;
            }
        }
    }
 
    // If no window found
    if (start_index == -1)
    {
       cout << "No such window exists";
       return "";
    }
 
    // Return substring starting from start_index
    // and length min_len
    return S.substr(start_index, min_len);
}
 

int main()
{
    string S = "tutorial cup";
    string T = "oti";
 
    cout << "Smallest window is : "<< findSubString(S, T)<<endl;
    return 0;
}

arayış