Largest Palindromic Substring
-
amitsaharana 10 years ago 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.
-
ebs_cbn 2 years ago Solution Explained:
-
webpropopuli 6 years ago 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.
-
aueret 7 years ago 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; }
-
koushik390 7 years ago 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; }
}
Sort 15 Discussions, By:
Please Log In in order to post a comment