C++ में सबसे छोटा सबएरे ढूंढें जिसमें सभी एलिमेंट्स उसी क्रम में हों

मान लीजिए हमारे पास आकार m और n के दो ऐरे हैं, कार्य पहले ऐरे में न्यूनतम लंबाई का सबएरे ढूंढना है, जिसमें दूसरे ऐरे के सभी एलिमेंट्स हों। दूसरा ऐरे में एलिमेंट्स बड़े ऐरे में नॉन-कंटीग्यूअस लेकिन क्रम समान होना चाहिए। तो यदि दो ऐरे हैं जैसे A = [2, 2, 4, 5, 8, 9], और B = [2, 5, 9], तो आउटपुट 5 होगा। क्योंकि A का सबसे छोटा सबएरे [2, 4, 5, 8, 9] होगा। यहां [2, 5, 9] जैसे सभी एलिमेंट्स उसी क्रम में हैं। तो आकार 5 है।

हम इसे पहले एलिमेंट की जांच करके हल कर सकते हैं जो दूसरे ऐरे के पहले एलिमेंट से मेल खाता है। जब पहला एलिमेंट मेल खाता है, फिर हम दूसरे ऐरे के बाकी एलिमेंट्स को मुख्य ऐरे में मिलाते हैं, जब सभी एलिमेंट्स मेल खाते हैं, तो जरूरत पड़ने पर लंबाई अपडेट करें। ऐसा करने के बाद सबएरे की न्यूनतम लंबाई वापस करें।

उदाहरण

#include 
using namespace std;

int lengthMinSubarray(int A[], int n, int B[], int m) {
    int res = INT_MAX;
    for (int i = 0; i < n - m + 1; i++) {
        if (A[i] == B[0]) {
            int j = 0, idx = i;
            for (; idx < n; idx++) {
                if (A[idx] == B[j])
                    j++;
                if (j == m)
                    break;
            }
            if (j == m && res > idx - i + 1)
                res = (idx == n) ? idx - i : idx - i + 1;
        }
    }
    return res;
}

int main() {
    int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
    int B[] = { 5, 5, 7 };
    int n = sizeof(A)/sizeof(A[0]);
    int m = sizeof(B)/sizeof(B[0]);
    cout << "Minimum length of subarray: " << lengthMinSubarray(A, n, B, m);
}

आउटपुट

Minimum length of subarray: 3