पायथन में समान सबस्ट्रिंग्स के जोड़े की संख्या खोजने का प्रोग्राम

मान लीजिए हमें दो स्ट्रिंग्स दी गई हैं, दोनों लोअरकेस अल्फाबेट से बनी हैं। हमें उन क्वाड्रपल्स (p, q, r, s) की संख्या ढूंढनी है जो निम्नलिखित शर्तों को पूरा करते हैं:

• 0 <= p <= q <= पहली स्ट्रिंग की लंबाई।
• 0 <= r <= s <= दूसरी स्ट्रिंग की लंबाई।
• पहली स्ट्रिंग में इंडेक्स p से शुरू होकर इंडेक्स q पर खत्म होने वाला सबस्ट्रिंग, दूसरी स्ट्रिंग में इंडेक्स r से शुरू होकर इंडेक्स s पर खत्म होने वाले सबस्ट्रिंग के बराबर होना चाहिए।
• q - r का मान उन सभी क्वाड्रपल्स में न्यूनतम संभव होना चाहिए जो उपरोक्त को पूरा करते हैं।

हमें ऐसे क्वाड्रपल्स की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट firstString = 'hgfn', secondString = 'gfrt' है, तो आउटपुट 2 होगा।

दो क्वाड्रपल्स (1, 1, 0, 0) और (2, 2, 1, 1) हैं जो शर्तों को पूरा करते हैं और q - r का न्यूनतम मान रखते हैं।

हल करने के चरण

1. left := आकार 26 की सूची जिसमें मान infinity हो।
2. right := आकार 26 की सूची जिसमें मान -1 हो।
3. res := 0
4. mi := infinity
5. पहली स्ट्रिंग में प्रत्येक इंडेक्स i और कैरेक्टर ch के लिए:
   • left[ord(ch) - ord('a')] := min(left[ord(ch) - ord('a')], i)
6. दूसरी स्ट्रिंग में प्रत्येक इंडेक्स i और कैरेक्टर ch के लिए:
   • right[ord(ch) - ord('a')] := max(right[ord(ch) - ord('a')], i)
7. i को 0 से 25 तक लूप चलाएं:
   • यदि left[i] != -1, तो mi := min(mi, left[i] - right[i])
8. i को 0 से 25 तक लूप चलाएं:
   • यदि left[i] != infinity और right[i] != -1, तो:
     • यदि left[i] - right[i] == mi, तो res := res + 1
9. res वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(firstString, secondString):
    left = [float('inf')] * 26
    right = [-1] * 26
    res = 0
    mi = float('inf')
    for i, ch in enumerate(firstString):
        left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
    for i, ch in enumerate(secondString):
        right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
    for i in range(26):
        if left[i] != -1:
            mi = min(mi, left[i] - right[i])
    for i in range(26):
        if left[i] != float('inf') and right[i] != -1:
            if left[i] - right[i] == mi:
                res += 1
    return res

print(solve('hgfn', 'gfrt'))

इनपुट

'hgfn', 'gfrt'

आउटपुट

2