9 days ago

Rohit • 40

Hyderabad

Question: Symmetric Round-Trip Itinerary

Problem Statement:

An airline planner has an itinerary string representing a sequence of airport codes joined by hyphens, e.g.,

"SFO-LAX-SEA-LAX-SFO-BOS"

A subsequence of this itinerary is obtained by deleting zero or more airport codes without changing the order of the remaining codes. Find the length of the longest subsequence of airport codes that reads the same forwards and backwards (i.e., a palindromic subsequence), so the planner can identify the largest symmetric round-trip segment.

Example:

itinerary = "NYC-LAX-CHI-LAX-NYC-BOS"

Output: 5 // One palindromic subsequence is ["NYC", "LAX", "CHI", "LAX", "NYC"]

Constraints:

• 1 <= {number of codes} <= 4000
• Codes are fixed-length (3 uppercase letters)
• Input should be string
• Output should be integer

Sample Input:

MNO-PQR-STU-PQR-MNO

Sample Output:

5