Detect permutation in linked list

Question

Given a linked list and a string, determine if any contiguous sublist of the linked list is a permutation (anagram) of the given string. The linked list nodes contain characters, and you should return true if such a permutation exists, or false otherwise. The solution should efficiently handle the linked list traversal and character frequency counting.

Codemia · Accepted Answer

To determine if any contiguous sublist of the linked list is a permutation of the given string, we can leverage a frequency counting approach. The problem can be effectively solved using the sliding window technique combined with a hash map (or dictionary) to keep track of character counts. This is applicable here because we need to continuously check segments of the linked list against the character frequency of the input string. The key insight is that if two strings are permutations of each other, they will have identical character frequencies.

1. **Character Frequency Map**: First, create a frequency map for the characters in the input string. For example, for the string 'abc', the frequency map would be `{'a': 1, 'b': 1, 'c': 1}`.

2. **Sliding Window Setup**: Initialize two pointers to represent the current window in the linked list that we are examining. We will also maintain a frequency map for the characters in the current window of the linked list.

3. **Expand and Contract Window**: As we traverse the linked list:
   - Expand the window by adding the current character to the current window frequency map.
   - If the window size exceeds the length of the input string, shrink the window from the left.
   - After each adjustment, compare the current window frequency map with the frequency map of the string. If they match at any point, return `True`.

4. **Complete Traversal**: If the end of the linked list is reached without finding a matching frequency map, return `False`.

For example, given the linked list representing characters 'c', 'a', 'b', and the string 'abc', our sliding window will check:
- Window 'c': Not a match
- Window 'ca': Not a match
- Window 'cab': Match found!

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def is_permutation_in_linked_list(head: ListNode, s: str) -> bool:
    from collections import Counter
    s_count = Counter(s)
    s_len = len(s)
    current_count = Counter()
    left = 0
    right = 0

while right < s_len:
        current_count[head.val] += 1
        right += 1
        head = head.next

if current_count == s_count:
        return True

while head:
        current_count[head.val] += 1
        current_count[head.val] -= 1
        if current_count[head.val] == 0:
            del current_count[head.val]
        left += 1
        head = head.next

if current_count == s_count:
            return True

return False
```

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because we make a single pass through the linked list to build the character frequency map and then at most two passes to check for permutations. The space complexity is O(k), where k is the size of the character set for the string (usually constant if the input is limited to lowercase letters or a fixed alphabet).

1. **Empty Linked List**: If the linked list is empty, return `False` since no permutations can exist.
2. **Empty String**: If the input string is empty, the function should return `True` only if the linked list is also empty. If the list has characters, return `False`.
3. **Linked List Shorter than String**: If the linked list has fewer characters than the input string, return `False` immediately.
4. **Non-overlapping Characters**: If the linked list contains characters that do not match the string at all, ensure the algorithm correctly identifies this.

Detect permutation in linked list

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string