Detect anagram in linked list

Question

Given a linked list of characters, determine if any contiguous subsequence of the linked list forms an anagram of a given target string. The function should return true if such an anagram exists, and false otherwise.

Codemia · Accepted Answer

To determine if any contiguous subsequence of a linked list forms an anagram of a given target string, we can use the **sliding window** approach. This method is suitable here because we can maintain a window of characters in the linked list that matches the length of the target string. By comparing the frequency of characters in the current window to the frequency of characters in the target string, we can efficiently check for anagrams. The sliding window will move through the linked list, dynamically updating character counts as we progress.

1. **Count the characters in the target string**: Use a frequency dictionary to store the count of each character in the target string.
2. **Initialize a sliding window**: Set up pointers to manage a window of characters in the linked list. The size of this window will match the length of the target string.
3. **Traverse the linked list**: Iterate through the linked list while maintaining a count of characters in the current window. 
   - For each new character added to the window, update the count in a dictionary.
   - If the window exceeds the target string's length, remove the character that falls out of the window.
4. **Compare counts**: After updating the counts for each window position, compare the frequency dictionary of the current window with that of the target string.
5. **Return result**: If a match is found during the traversal, return true; if the end of the list is reached without a match, return false.

**Example**: For linked list characters 'a', 'b', 'c', 'a', 'n', 'a' and target string 'nab', the windows would be:
- 'abc' -> counts: {'a': 1, 'b': 1, 'c': 1} (not an anagram)
- 'bca' -> counts: {'b': 1, 'c': 1, 'a': 1} (not an anagram)
- 'can' -> counts: {'c': 1, 'a': 1, 'n': 1} (not an anagram)
- 'ana' -> counts: {'a': 2, 'n': 1} (not an anagram)
- 'nab' -> counts: {'n': 1, 'a': 1, 'b': 1} (anagram found!)

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

def detect_anagram(head: ListNode, target: str) -> bool:
    from collections import Counter
    target_count = Counter(target)
    target_length = len(target)
    window_count = Counter()
    current = head
    start = 0
    end = 0

while current:
        # Add the current character to the window count
        window_count[current.val] += 1
        end += 1

# If the window size exceeds the target length, shrink from the start
        if end > target_length:
            start_char = head.val
            window_count[start_char] -= 1
            if window_count[start_char] == 0:
                del window_count[start_char]
            head = head.next
            start += 1

# Check if we have a valid anagram
        if end - start == target_length and window_count == target_count:
            return True

current = current.next

return False
```

The **time complexity** of this approach is O(n + m), where n is the length of the linked list and m is the length of the target string. We traverse the linked list once, and for each window, we perform constant-time dictionary operations.
The **space complexity** is O(m) for storing the frequency count of the target string and the current window, where m is the number of unique characters in the target string.

1. **Empty linked list**: If the linked list is empty, return false since no anagram can be formed.
2. **Target string is empty**: If the target string is empty, return true since an empty string can be considered an anagram of an empty string.
3. **Target string longer than linked list**: If the target string's length exceeds the linked list's length, return false as no subsequence can match.
4. **Single character linked list**: If the linked list has a single character and it matches the target, return true; otherwise, return false.

Detect anagram in linked list

Vercel

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

Vercel 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