मान लीजिए हमारे पास एक स्ट्रिंग S है। हमें S में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई ढूंढनी है। हम मान रहे हैं कि स्ट्रिंग S की लंबाई 1000 है। उदाहरण के लिए, यदि स्ट्रिंग "BABAC" है, तो सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग "BAB" है और इसकी लंबाई 3 है।
समाधान दृष्टिकोण (डायनामिक प्रोग्रामिंग)
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- स्ट्रिंग की लंबाई के बराबर क्रम का एक वर्ग मैट्रिक्स परिभाषित करें और इसे False से भरें।
- मुख्य विकर्ण के एलिमेंट्स को True सेट करें, यानी DP[i][i] = True सभी i के लिए 0 से length-1 तक।
- start = 0 और max_length = 1 आरंभ करें।
- सबस्ट्रिंग की लंबाई l के लिए 2 से length of S + 1 तक लूप चलाएं:
- प्रारंभिक इंडेक्स i के लिए 0 से length of S - l + 1 तक लूप चलाएं।
- end = i + l की गणना करें।
- यदि l == 2 है:
- यदि S[i] == S[end-1], तो DP[i][end-1] = True, max_length = l, और start = i सेट करें।
- अन्यथा (l > 2):
- यदि S[i] == S[end-1] और DP[i+1][end-2] True है, तो DP[i][end-1] = True, max_length = l, और start = i सेट करें।
- max_length लौटाएं।
पायथन कार्यान्वयन
class Solution(object):
def solve(self, s):
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = True
max_length = 1
start = 0
for l in range(2, len(s)+1):
for i in range(len(s)-l+1):
end = i + l
if l == 2:
if s[i] == s[end-1]:
dp[i][end-1] = True
max_length = l
start = i
else:
if s[i] == s[end-1] and dp[i+1][end-2]:
dp[i][end-1] = True
max_length = l
start = i
return max_length
ob = Solution()
print(ob.solve('BABAC'))
इनपुट
"ABBABBC"
आउटपुट
5