Largest Palindromic Substring

Sort 15 Discussions, By:

Sorry, you do not have a permission to answer to this question.

  • amitsaharana 10 years ago + 0 comments

    My submission has been removed. I tried code from a published source for the Manacher's algorithm(only the algorithm code) giving proper credits. If you expect to write a standard algorithm code by yourself, it should have been clearly mentioned like in base32 decoder question.

    Secondly, codeforces and topcoder both have clear rules regarding published codes. For example see here: http://codeforces.com/blog/entry/456. It clearly states that published codes before start of round e.g. on e-maxx.ru is allowed because everyone has access to it. No such rule is mentioned on Hackerrank.

    Thirdly, even then I made another submission, the 2nd one writing the whole algorithm by myself(3067390). This submission has not been taken into account.

    So, if Hackerrank follows the same published code policy like all other sites, then my 1st submission is valid. In any case, my 2nd submission is valid. Kindly do the needful.

    Add Reply Preview cancel

    Sorry, you do not have a permission to answer to this question.

    • ebs_cbn 2 years ago + 0 comments

      Solution Explained:

      https://youtube.com/live/lsM54hRs4CU

      Add Reply Preview cancel

      Sorry, you do not have a permission to answer to this question.

      • webpropopuli 6 years ago + 0 comments

        In JS, I'm passing all testcases except #7, It looks like #8 is a boundary test and I got that working easy enough, but I can't make this fast enough for #7. And this is after I refactored a 30% speed improvement.

        I think I need to destructure my inner loop but I'm wondering if my algorithm is just flawed for large testcases only.

        Add Reply Preview cancel

        Sorry, you do not have a permission to answer to this question.

        • aueret 7 years ago + 0 comments

          quite brute-force and ugly but working 100 percent:

          #include <cmath>
          #include <cstdio>
          #include <vector>
          #include <iostream>
          #include <algorithm>
          using namespace std;
          
          string pal_try(const string &word, int left, int right)
          {
              if (left<0 || right>=word.size())
                  return "";
              if (word[left]==word[right])
                  return pal_try(word, left-1, right+1)+word[left];
              return "";
          }
          
          bool all_the_same(const string &word)
          {
              if (word.empty()) return false;
              return word.find_first_not_of(word[0]) == std::string::npos;
          }
          
          void chose_max(int left, int right, const string &word, string &mpl)
          {
              string pal = pal_try(word, left, right);
              if (pal.size() > mpl.size())
              {
                  mpl = pal;
                  if (left == right)
                      mpl = pal.substr(0, pal.size()-1); 
                  reverse(pal.begin(), pal.end());
                  mpl += pal;
              }
          }
          
          string find_max_pal(const string &word)
          {
              string mpl = "";
              for( int i=0; i<word.size(); ++i)
              {
                  chose_max(i, i, word, mpl);
                  chose_max(i-1, i, word, mpl);
                  chose_max(i, i+1, word, mpl);
              }
              return mpl;
          }
          
          int main() 
          {
              string word;
              cin >> word;
              if (all_the_same(word))
              {
                  cout << word;
                  return 0;
              }
              
              string mpl = find_max_pal(word);
              cout << mpl;
              return 0;
          }
          

          Add Reply Preview cancel

          Sorry, you do not have a permission to answer to this question.

          • koushik390 7 years ago + 0 comments

            Here is my solution all cases passed

            import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

            public class Solution {

            public static void main(String[] args) {
                /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
                Scanner scan = new Scanner(System.in);
                String s = scan.nextLine();
                long x=s.chars().distinct().count();
                if(x==1){
                    System.out.println(s);
                }else{
                    isPal(s);
                }
            
            }
            public static void isPal(String s) {
                HashSet<String> pals = new HashSet<>();
                int count=0;
                int max = -1;
                String maxs = "";
                for(int i=0;i<s.length();i++) {
                    for(int j=0;i-j>=0 && j+i<s.length();j++) {
                        if(s.charAt(i-j)==s.charAt(i+j)) {
                            String temp = s.substring(i-j, i+j+1);
                            if(!pals.contains(temp)) {
                                pals.add(temp);
                                if(maxs==""){
                                    maxs=temp;
                                    max=temp.length();
                                }else{
                                    if(max<temp.length()){
                                        maxs=temp;
                                        max=temp.length();
                                    }
                                }
                                count++;
                            }
                        }else{
                            break;
                        }
                    }
                }
                for(int i=0;i<s.length();i++) {
                    for(int j=0;i-j>=0 && j+i+1<s.length();j++) {
                        if(s.charAt(i-j)==s.charAt(i+j+1)) {
                            String temp = s.substring(i-j, i+j+2);
                            if(!pals.contains(temp)) {
                                pals.add(temp);
                                if(maxs==""){
                                    maxs=temp;
                                    max=temp.length();
                                }else{
                                    if(max<temp.length()){
                                        maxs=temp;
                                        max=temp.length();
                                    }
                                }
                                count++;
                            }
                        }else{
                            break;
                        }
                    }
                }
            
                System.out.println(maxs);
                //return count;
            }
            

            }

            Add Reply Preview cancel

            Sorry, you do not have a permission to answer to this question.

            1. Challenge Walkthrough
              Let's walk through this sample challenge and explore the features of the code editor.1 of 6
            2. Review the problem statement
              Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
            3. Choose a language
              Select the language you wish to use to solve this challenge.3 of 6
            4. Enter your code
              Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
            5. Test your code
              You can compile your code and test it for errors and accuracy before submitting.5 of 6
            6. Submit to see results
              When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
            1. Check your score