14 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

5 minutes ago

admin 1.9k

Hyderabad

Problem Solution

Symmetric Round-Trip Itinerary

Overview

The objective is to find the Longest Palindromic Subsequence (LPS) of airport codes. Unlike a substring, a subsequence does not need to be contiguous; you can delete codes from the original itinerary as long as you maintain the relative order of the remaining ones. A "palindromic" subsequence reads the same forwards and backwards (e.g., ["SFO", "LAX", "SFO"]).

With N \le 4000 codes, a standard recursive approach with memoization or a 2D dynamic programming approach is required to solve this in O(N^2) time.

Approach

1. Tokenization: The input is a single string. First, split the string by the hyphen (-) delimiter to extract the 3-letter airport codes into a list or vector of strings.
2. Dynamic Programming State: Define a 2D array
   dp[n][n]
   , where
   dp[i][j]
   represents the length of the longest palindromic subsequence found in the segment of codes from index i to index j.
3. Base Cases:
   • Every single code is a palindrome of length 1:
     dp[i][i] = 1
     for all i.
4. Transitions: Iterate through the possible lengths of segments (from 2 up to N):
   • If the codes at the boundaries match (Code[i] == Code[j]):
     • They contribute 2 to the length of the palindrome found in the inner segment:
       dp[i][j] = dp[i+1][j-1] + 2
       .
   • If the codes do not match:
     • The LPS is the maximum length found by either excluding the left boundary or the right boundary:
       dp[i][j] = \max(dp[i+1][j], dp[i][j-1])
       .
5. Final Result: The value stored in
   dp[0][n-1]
   will be the length of the longest symmetric segment for the entire itinerary.

Time and Space Complexity

• Time Complexity: O(N^2) — We fill an N \times N table, and each cell takes O(1) time (string comparisons for 3-letter codes are effectively constant time).
• Space Complexity: O(N^2) — To store the DP table. For N=4000, this consumes roughly 64 MB of memory, which fits well within standard limits.

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

int longestSymmetricItinerary(string itinerary) {
    // Step 1: Tokenize the itinerary by hyphens
    vector<string> codes;
    stringstream ss(itinerary);
    string token;
    while (getline(ss, token, '-')) {
        if (!token.empty()) {
            codes.push_back(token);
        }
    }

    int n = codes.size();
    if (n == 0) return 0;

    // Step 2: Initialize DP table
    // dp[i][j] = length of LPS in codes[i...j]
    // Using a 1D vector to simulate 2D for memory efficiency if needed,
    // but N=4000 fits in a standard 2D vector (64MB).
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // Every single airport is a palindrome of length 1
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Step 3: Build the DP table for segments of increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            
            if (codes[i] == codes[j]) {
                // If boundary codes match, they add 2 to the inner result
                // If len is 2, dp[i+1][j-1] is effectively 0
                dp[i][j] = (len == 2) ? 2 : dp[i + 1][j - 1] + 2;
            } else {
                // Otherwise, take the maximum of moving either boundary
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    // The result for the full range
    return dp[0][n - 1];
}

int main() {
    string input;
    if (cin >> input) {
        cout << longestSymmetricItinerary(input) << endl;
    }
    return 0;
}