Detect anagram in linked list

Question

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

Codemia · Accepted Answer

To determine if any contiguous sublist of a linked list forms an anagram of a given string, we can leverage the concept of frequency counting and the sliding window technique. The sliding window approach is particularly useful here since we need to check each contiguous sublist of the linked list while maintaining a count of characters. The main reason for choosing this pattern is that it allows us to efficiently track the frequency of characters in the current window of the linked list, while also comparing it against the frequency of characters in the target string.

1. **Character Frequency Count**: Start by creating a frequency map (dictionary) for the target string. For example, if the string is 'abc', the frequency map would be {'a': 1, 'b': 1, 'c': 1}.

2. **Sliding Window Setup**: Use two pointers to create a sliding window that traverses the linked list. One pointer (`start`) marks the beginning of the window, and another pointer (`end`) marks the current character being processed in the linked list.

3. **Window Expansion and Contraction**: As we move the `end` pointer, we include the current character in the window and update the frequency count. If the window size exceeds the length of the target string, we move the `start` pointer to shrink the window from the left.

4. **Frequency Comparison**: After updating the window, compare the character frequency of the current window with that of the target string. If they match at any point, we have found an anagram.

5. **Return Result**: If no anagram is found by the time we traverse the linked list, return false.

Here’s the Python implementation of the above approach:

```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:
        # Expand the window by adding the end character
        current_count[end.val] += 1
        length += 1

# If the window size exceeds the target length, contract from the start
        while length > target_length:
            current_count[start.val] -= 1
            if current_count[start.val] == 0:
                del current_count[start.val]
            start = start.next
            length -= 1

# Check if current window matches the target frequency count
        if current_count == target_count:
            return True

end = end.next

return False
```
This code defines a ListNode class for the linked list and a function `detect_anagram` that checks for anagrams in 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 each node once with the `end` pointer, and the inner while loop will not run more than n times in total across all iterations. The space complexity is O(m), where m is the size of the character set present in the target string. In the worst case, we might need to store the frequency of all characters in the target string.

1. **Empty Linked List**: If the linked list is empty, the function should return false since there's no sublist to form an anagram.
2. **Target String Length Greater Than Linked List Length**: If the length of the target string is greater than the length of the linked list, it should return false immediately.
3. **Single Character Lists**: If the linked list contains a single character and the target string is also a single character, it should return true if they match and false otherwise.
4. **Special Characters**: If the target string contains special characters, ensure that the linked list characters can match those as well.

Detect anagram in linked list

Salesforce

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

Salesforce 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