रेफ़रेंस स्ट्रिंग (The Reference String)
आपको n स्ट्रिंग्स की एक लिस्ट दी गई है, जिनमें से हर एक स्ट्रिंग लोअरकेस लैटिन अक्षरों से बनी होती है। हम ऐसी किसी स्ट्रिंग s (लोअरकेस लैटिन अक्षरों तथा कैरेक्टर # से बनी) को रेफ़रेंस स्ट्रिंग (reference string) कहेंगे यदि लिस्ट में मौजूद हर स्ट्रिंग के लिए, s में कोई ऐसा इंडेक्स i चुना जा सकता है ताकि ≠ # हो, और i से लेकर s में अगले # (इसे शामिल किए बिना) तक के सभी इंडेक्स चुनने पर वही स्ट्रिंग बन जाए। साथ ही, रेफ़रेंस स्ट्रिंग हमेशा कैरेक्टर # पर समाप्त होनी चाहिए।
दी गई लिस्ट के आधार पर, ऐसे प्रोग्राम को लिखें जो सबसे छोटी लंबाई वाली उस रेफ़रेंस स्ट्रिंग की लंबाई बताए, जो उपरोक्त शर्त को पूरा करती हो।
इनपुट (Input)
इनपुट की पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 100 000) दिया गया है, जो लिस्ट में मौजूद स्ट्रिंग्स की संख्या दर्शाता है।
अगली n पंक्तियों में ये स्ट्रिंग्स दी जाती हैं। प्रत्येक स्ट्रिंग लोअरकेस लैटिन अक्षरों से बनी है और इसकी लंबाई अधिकतम 10 होती है।
आउटपुट (Output)
प्रोग्राम को केवल एक पूर्णांक प्रदर्शित करना चाहिए, जो उपरोक्त शर्तों को पूरी करने वाली सबसे छोटी रेफ़रेंस स्ट्रिंग की लंबाई हो।
उदाहरण (Examples)
Input | Output |
6
found
profound
ground
round
wound
und | 22 |
3
ab
bc
cd | 9 |
स्पष्टीकरण (Explanation)
- Example 1: सबसे छोटी रेफ़रेंस स्ट्रिंग में से एक ‘ground#profound#wound#’ है।
- Example 2: सबसे छोटी रेफ़रेंस स्ट्रिंग में से एक ‘ab#bc#cd#’ है।
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB