Detect anagram in linked list

Question

Given a linked list of characters, determine if any contiguous sublist forms an anagram of a given target string. The function should return true if such an anagram exists within the linked list, and false otherwise. The solution should efficiently traverse the linked list while maintaining a count of character frequencies.

Codemia · Accepted Answer

The problem requires us to determine if any contiguous sublist of characters within a linked list forms an anagram of a given target string. The underlying pattern here is the **sliding window technique**, which is particularly effective for problems involving contiguous subsequences. We can maintain a character frequency count for both the target string and the current window of characters in the linked list. As we slide the window over the linked list, we can check if the frequency counts match, indicating that the characters are anagrams.

1. **Count the Frequency of the Target String**: First, we will create a frequency counter for each character in the target string. For example, if the target is 'abc', our frequency map will be `{ 'a': 1, 'b': 1, 'c': 1 }`.

2. **Initialize Two Pointers**: Set two pointers; one for the start of the current window (`start`) and one for the end of the current window (`end`). Begin both at the head of the linked list.

3. **Expand the Window**: Move the `end` pointer to include characters in the current window. For each character added, update the frequency count of the current window.

4. **Check Window Size**: Once the window size matches the length of the target string, check if the frequency counts match the target.

5. **Slide the Window**: If the counts do not match, increment the `start` pointer to reduce the window size from the left, and update the frequency counts accordingly. Repeat until the end of the linked list is reached.

6. **Return Result**: If at any point the frequency counts match, return `true`. If the traversal ends without finding any match, return `false`.

Here’s the Python implementation for the solution:

```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)

current_count = Counter()
    start = head
    end = head
    length = 0

while end:
        current_count[end.val] += 1
        length += 1

if length > target_length:
            current_count[start.val] -= 1
            if current_count[start.val] == 0:
                del current_count[start.val]
            start = start.next
            length -= 1

if length == target_length and current_count == target_count:
            return True

end = end.next

return False
```
This implementation effectively manages the character frequency counts and checks for anagrams as we traverse the linked list.

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 with the `end` pointer once, making it linear in nature. The space complexity is **O(m)**, where `m` is the size of the character set (in this case, the maximum unique characters in the target string). Since we are using two frequency counters, the space used is proportional to the number of unique characters.

1. **Empty Linked List**: If the linked list is empty, the function should return `false` since there cannot be any anagrams.
2. **Target Longer than Linked List**: If the target string is longer than the linked list, return `false` as it's impossible for the linked list to contain such an anagram.
3. **All Characters Match**: If the linked list contains only the characters that form the target string, ensure that the function returns `true`.
4. **Case Sensitivity**: Make sure the solution is aware of character cases; 'a' and 'A' should be treated as different characters unless specified otherwise.

Detect anagram in linked list

Visa

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

Visa 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