Longest Even Length Palindromic Substring (with unique adjacent characters except for the center 2 letters)

You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern: X1,X2,X3…Xn,Xn,…X3,X2,X1 where Xi is some character of S. The only constraint is that no adjacent character should be the same except Xn, that is Xi != X(i+1) for all 1<=i< n.

Input: The string: S

Output: The integer: 2n

Constraint: 1<=|S|<=10^3

Sample input 1: “acdbdea”

Sample output 1: 4

Explanation: “adda” is the longest subsequence following the given pattern.

Sample input 2: “abbacdeedc”

Sample output 2: 6

Explanation: “cdeedc” is the longest subsequence following the given pattern.

Sample input 3: “taker”

Sample output 3: 0

Explanation: No subsequence follows the given pattern.


This question was asked in a coding interview and I didn’t know how to solve it. I understood how to find longest palindromic sub sequence but don’t know how to implement the unique adjacent character part. Please help. pseudo code is fine

How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?

Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.

I tried to start by coming up with the base cases, subproblem and recurrence but having trouble picturing the problem space or the most efficient way to do it. (For example, is it best to find the longest palindromic continuous subsequence first, or rather find the earliest one first?)

For example:

Sequence: [A, B, A, G, C, C, G, T, O, O, T ] is made up from 3 subsequences, namely [A, B, A] + [G, C, C, G] + [T, O, O, T]

So, therefore, my output for this example would be 3.

Thanks in advance!

Practical applications of the palindromic substring problem?

The longest palindromic substring problem is certainly an interesting intellectual exercise, and seems to be popular in coding interviews in industry. As an interesting puzzle, its popularity for interviews is not too hard to understand–it’s not too hard to find an $ O(N^2)$ solution, and if someone manages to come up with a linear time solution, they’re probably either a genius or at least well-read, which is arguably as valuable.

Given the apparent frivolity of the problem, however, it seems like a surprising amount of effort has gone in to analyzing it. There are at least three published linear-time solutions (by Manacher, Jeuring, and Gusfield). But, is it actually useful for anything? Are there other problems in which finding a palindromic substring is a necessary step? And in the absence of a direct application, did any of the known solutions to this problem reveal new techniques that have been applicable elsewhere?

Calculate the largest palindromic number from the product of two 6-digit numbers (100000 to 999999)

Are there any efficient ways to solve this problem, for example using bitwise operator?

    public static boolean isPal(long num)      {         String numStr = Long.toString(num);         String rNumStr = "";          boolean result = false;          for (int i = numStr.length() - 1; i >= 0 ; --i)             rNumStr += numStr.charAt(i);          //System.out.println(numStr + "," + rNumStr);         try          {             if (Long.parseLong(numStr) == Long.parseLong(rNumStr))                 result = true;             else                   result = false;         }catch (NumberFormatException e) {             //System.err.println("Unable to format. " + e);         }         return result;      }      public static void calcPal(int rangeMin, int rangeMax)     {         long maxp = 0, maxq = 0, maxP = 0;         for (int p = rangeMax; p > rangeMin; p--)             for (int q = rangeMax; q > rangeMin; q--)             {                 long P = p * q;                 if (isPal(P))                     if (P > maxP)                     {                         maxp = p; maxq = q; maxP = P;                     }             }         System.out.println(maxp + "*" + maxq + "=" + maxP);     }      public static void main(String[] args)      {         calcPal(10, 99);         calcPal(100, 999);         calcPal(9000, 9999);         calcPal(10000, 99999);         calcPal(990000, 999999);     } 

The largest palindrome which can be made from the product of two 2-digit (10 to 99) numbers is 9009 (91 × 99). Write a function to calculate the largest palindromic number from the product of two 6-digit numbers (100000 to 999999).

Palindromic paritions – solution

Task

Find the smallest number of cuts required to break a string into a set of valid palindromes. For example:

  • ababbbabbababa becomes a|babbbab|b|ababa (cuts = 3)
  • partytrapb becomes partytrap|b (cuts = 1)

Note: all strings of length 1 are palindromes as a single character reads the same forward and backward

import re  def find_paritions(lst, word, running=[]):     for (index,item) in enumerate(lst):         if index > 0:             running.pop()         running = running + [item]         if item[1] == len(word):             complete_paths.append(running)             return          to_explore = []         end = item[1]         for item_next in list_parition_index:             if item_next[0] == end:                 to_explore.append(item_next)         if len(to_explore) == 0:              return          find_paritions(to_explore,word,running)      return complete_paths  complete_paths=[]  word = "ababbbabbababa" start = 0 end = 1 parition_count =0 list_parition_index = [] for start in range (len(word)):     end=start+1     while end < len(word) + 1:         if word[start:end] == word[start:end][::-1]:             list_parition_index.append([start,end])             end +=1         else:             end +=1 list_zeroes = [x for x in list_parition_index if x[0] == 0]   x = find_paritions (list_zeroes,word) print(f"The total number of divisions required is {len(min(x,key=len))-1}") print(min(x,key=len))