Linkedin | SRE | Coding OA and Solutions | Set-10 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

For a string s and an integer k , a selection of substrings is valid if the following conditions are met :

 

• The length of every substring is greater than or equal to k.
• Each substring is a palindrome.
• No two substrings overlap.

 

Determine the maximum number of valid substrings that can be formed from s.

 

Note: A substring is a group of adjacent characters in a string.
A palindrome is a string that reads the same backwards and forwards.

 

Example:
s="aababaabce"
k=3
output-2
strings are aba and baab

 

Constraints:
1<=|s|<=2x10^3
1<=k<=|s|

 

Example 01:
s="ababaeocco"
k=4
output-2
strings are ababa and occo

 

Example 02:
s="aaaaabb"
k=2
output-3
strings are aa , aa and bb

Answer 2

O(n) solutuon.

 

1. use Manacher's algorithm to find all the palindrome centers and lengths.
2. convert centers and lengths to intervals, if a length>k, reduce it to k or k+1. say, if s[4:10] is a palindrome, for k=2, convert it to [6,8]
3. the intervals should be naturally sorted, and then use sweep line to count the max # of non-overalpped intervals.