मैं किसी दिए गए स्ट्रिंग में सबसे लंबे समय तक व्यक्तिगत वर्ण पैलिंड्रोम को कुशलतापूर्वक कैसे निर्धारित करूं?

Question

लंबाई की एक स्ट्रिंग को देखते हुए एन युक्त वर्ण [ए-जेड], मैं एक व्यक्तिगत चरित्र के लिए सबसे लंबा पालिंड्रोम कैसे निर्धारित करूं?

मैं एक उदाहरण के साथ इस उदाहरण देकर स्पष्ट करना होगा:

को देखते हुए स्ट्रिंग: स्ट्रिंग का विश्लेषण करने में JOHNOLSON , हम पाते हैं कि हम चरित्र O ऐसी है कि स्ट्रिंग JOHN तरह लग रहा है के साथ एक विलोमपद है OLSON। O के लिए विलोमपद अनिवार्य रूप से की तरह O--O--O देख लंबाई 7 की है। इसके अलावा, नोटिस N साथ विलोमपद कि वहाँ, लेकिन यह केवल लंबाई की है 6.

एक अन्य उदाहरण है को देखते हुए स्ट्रिंग: ABCJOHNOLSON ही परिणाम से ऊपर के रूप में लंबाई 7 की तरह लग रही के O की की विलोमपद साथ देता है O--O--O।

हालांकि, दिए गए स्ट्रिंग ABCJOHNOLSONDA, साथ सबसे लंबे समय तक व्यक्तिगत चरित्र विलोमपद चरित्र A तरह A------------A देख के साथ लंबाई 14 वर्ष की है।

अन्य सरल उदाहरणों में शामिल हैं:

ABA ->A-A (लंबाई 3)

ABAXYZ ->A-A (लंबाई 3)

ABAXYZA ->A---A (लंबाई 5), नहीं लंबाई 7 क्योंकि A-A---A पत्र A के लिए विलोमपद नहीं है।

अंतिम उदाहरण पर विशेष ध्यान दें क्योंकि यह समस्या के सूक्ष्म बारीकियों में से एक को दर्शाता है।

Answer 1

आप इसे रैखिक समय में कर सकते हैं, यह कोड नमूना के साथ here का वर्णन किया गया है।

Answer 2

यहां मैं क्या आया, मुझे नहीं पता कि यह कितना कुशल हो सकता है।

 
For every letter in the alphabet, 
    Find the first and last occurrence of this letter. 
    While the substring is not a palindrome for that letter (easy to check), 
    find the next letter on both sides so that every possible combination is 
    checked. Take the longest one and store it. 
Take the longest one. 

Answer 3

निश्चित रूप से इष्टतम नहीं है। मानता है इनपुट स्ट्रिंग सभी लोअरकेस है।

using System; 
using System.Collections.Generic; 

public class LongestPalindrome 
{ 
    public int longest(string s) 
    { 
     Dictionary<char, List<int>> indices = 
      new Dictionary<char, List<int>>(); 

     // find all indices for each letter 
     for (int i = 0; i < s.Length; i++) 
     { 
      char c = s[i]; 
      if (!indices.ContainsKey(c)) 
        indices.Add(c, new List<int>()); 
      indices[c].Add(i); 
     } 

     int max = Int32.MinValue; 

     for (int i = (int)'a'; i <= (int)'z'; i++) 
     { 
      char c = (char)i; 

      // in case a letter didn't appear at all in the input string 
      if (!indices.ContainsKey(c)) continue; 

      List<int> indexList = indices[c]; 

      // in case a letter appeared only once in the input string 
      if (indexList.Count == 1) max = Math.Max(max, 1); 

      for (int j = 0; j < indexList.Count; j++) 
      { 
       for (int k = j + 1; k < indexList.Count; k++) 
       { 
        int dist = indexList[k] - indexList[j] + 1; 
        string sub = s.Substring(indexList[j], dist); 
        if (isPalendrome(sub, c)) 
             max = Math.Max(max, dist); 
       } 
      } 
     } 

     return max; 
    } 

    bool isPalendrome(string s, char c) 
    { 
     int i = 0; 
     while(i < s.Length - 1 - i) 
     { 
      if (s[i] != c && s[s.Length - 1 - i] != c) 
      { 
       i++; 
       continue; 
      } 
      if (s[i] != s[s.Length - 1 - i]) return false; 
      i++; 
     } 
     return true; 
    } 
}