Detect permutation in linked list

Question

Given a linked list and a string, determine if any contiguous subsequence of the linked list's values forms a permutation of the string. The linked list is composed of characters, and the output should indicate whether such a permutation exists (true or false).

Codemia · Accepted Answer

To determine if any contiguous subsequence of the linked list's values forms a permutation of a given string, we can utilize the **sliding window technique** combined with **character frequency counting**. This is appropriate here because we need to check various consecutive segments of the linked list for a match with the frequency of characters in the string. Since permutations have the same character counts, we can maintain a count of characters from both the string and the current window in the linked list and compare them.

1. Initialize a frequency counter for the string using a dictionary to count occurrences of each character. 
2. Create a sliding window of size equal to the length of the string and start from the beginning of the linked list. 
3. Use two pointers: one for the start of the window and one for the end. As the end pointer moves through the linked list:
   - Add the current character to the window's frequency count. 
   - If the window size exceeds the length of the string, remove the character at the start pointer from the frequency count and move the start pointer forward. 
4. After each modification, compare the frequency count of the window with that of the string. If they match, we have found a permutation and can return true. 
5. If we reach the end of the linked list without finding a match, return false. 
For example, if the linked list represents 'abcde' and the string is 'cba', we would check subsequences like 'abc', 'bcd', etc., looking at their character counts.

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

def is_permutation_in_linked_list(head, s):
    from collections import Counter
    s_count = Counter(s)
    len_s = len(s)
    current = head
    window_count = Counter()
    start = 0

for end in range(len_s):
        if current:
            window_count[current.value] += 1
            current = current.next

if window_count == s_count:
        return True

while current:
        window_count[head.value] -= 1
        if window_count[head.value] == 0:
            del window_count[head.value]
        window_count[current.value] += 1

head = head.next
        if window_count == s_count:
            return True

return False
```

The time complexity of this solution is **O(n)**, where **n** is the number of nodes in the linked list. This is because we traverse the linked list at most twice: once to build the initial window and once to slide through it. The space complexity is **O(m)**, where **m** is the number of unique characters in the string. This is due to the storage of character counts in the dictionary.

1. **Empty Linked List**: If the linked list is empty, return false since there are no characters to form a permutation. 
2. **Empty String**: If the string is empty, return true because an empty string is a permutation of an empty sequence. 
3. **Linked List Smaller than String**: If the linked list has fewer nodes than the length of the string, return false immediately. 
4. **All Characters Same**: If the string consists of the same character (e.g., 'aaa') and the linked list does not contain that character, return false.

Detect permutation in linked list

PayPal

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

PayPal 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