Katkat
Back

Remove duplicates and find constrained longest subsequence

SalesforceSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to manipulate linked structures to remove duplicates and your algorithmic efficiency in finding the longest string that satisfies two distinct containment constraints.

Part 1: Deduplication

Given the head of a singly linked list of integers, remove all duplicate nodes such that each value appears only once. The relative order of the nodes should be preserved.

# Definition for a singly-linked list node.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def remove_duplicates(head: ListNode) -> ListNode:
    pass

Part 2: Longest Constrained String

Given two strings s1 and s2, find the length of the longest string x such that x is a subsequence of s1 AND x is a substring of s2.

  • A substring is a contiguous sequence of characters within a string.
  • A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Examples

Example 1: Input: s1 = "abcde", s2 = "ace" Output: 3 Explanation: "ace" is a substring of "ace" and a subsequence of "abcde".

Example 2: Input: s1 = "banana", s2 = "nana" Output: 4

Constraints

  • Length of s1 and s2 are up to 1000.
  • s1 and s2 consist of lowercase English letters.

Hints

Hint 1

For the linked list, use a hash set to track seen values as you traverse the list.

Hint 2

For the string problem, note that the answer must be a substring of s2; you can iterate over all possible substrings of s2 and check if each is a subsequence of s1.

Hint 3

Checking if string A is a subsequence of string B can be done greedily in O(length of B) time.

Follow-up questions

  • How would you optimize the linked list removal if the input was already sorted?
  • What is the time complexity of the string solution if s2 has length N and s1 has length M?
  • Can you solve the string problem using a two-pointer approach or dynamic programming to achieve better than O(N^2 * M)?