DFS on string

Question

Implement a Depth-First Search (DFS) algorithm to explore all possible substrings of a given string. Your function should take a string as input and return a list of all unique substrings found within it. Ensure that the solution efficiently handles strings of varying lengths and characters.

Codemia · Accepted Answer

To tackle the problem of finding all unique substrings of a given string using DFS, we recognize that the problem can be represented as a tree where each node corresponds to a substring formed by extending the previous node's substring. The DFS pattern is suitable here because it allows for exploring all possible combinations of characters in a structured manner, ensuring that we can generate and collect unique substrings efficiently. We also need to manage duplicates due to repeated characters, hence a set will be used to store the substrings.

1. Initialize a set to store unique substrings.  
2. Create a recursive DFS function that takes the current start index and constructs substrings by iterating from the current index to the end of the string.  
3. For each substring generated, add it to the set.  
4. Call the DFS function for every starting index from 0 to the length of the string.  
5. After the DFS completes, convert the set to a list and return it.

**Example:** For the input string 'abc', we start with an empty substring and generate:  
- From index 0: 'a', 'ab', 'abc'  
- From index 1: 'b', 'bc'  
- From index 2: 'c'  
The unique substrings collected are: ['a', 'ab', 'abc', 'b', 'bc', 'c'].

```python
def unique_substrings(s):
    unique_subs = set()
    n = len(s)
    
    def dfs(start):
        # Explore all substrings starting from index 'start'
        for end in range(start + 1, n + 1):
            substring = s[start:end]
            unique_subs.add(substring)
            dfs(end)

for i in range(n):
        dfs(i)

return list(unique_subs)
```

The time complexity of this algorithm is O(n^2) because for each starting index, we potentially generate substrings that can take O(n) time, and we do this for each of the n indices. Thus, the overall complexity is O(n^2). The space complexity is O(n^2) as well since we store all unique substrings in a set, which could contain up to n(n+1)/2 substrings in the worst case where all characters are unique.

1. **Empty String**: If the input string is empty, the output should be an empty list.  
2. **Single Character String**: For input 'a', the output should be ['a'].  
3. **Repeated Characters**: For input 'aaa', the unique substrings should only be ['a', 'aa', 'aaa'].  
4. **Long Strings**: Ensure the function can handle longer strings efficiently, such as 'abcdefghij', without exceeding memory limits or causing timeouts.

DFS on string

Palo Alto Networks

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

Palo Alto Networks 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