Problem

Submissions

Hints & solutions

Discuss

Remove String

Moderate

0/80

Average time to solve is 35m

Contributed by

26 upvotes

Asked in companies

Problem statement

You have been given a linked list where each node has a single character. You have also been given a string 'STR'.

You have to remove all the occurrences of string STR from the linked list.

Note:

1. Start checking from the end of the linked list and not from the beginning. For example, if the linked list is ( a, b, a ,b, a)  and the string is equal to “aba” , then the answer should be (a b), not (b a).

2. After removing an occurrence check again for new formations.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an Integer 'T' which denotes the number of test cases.

The first line of each test case contains the elements of the singly linked list which are the characters not separated by a space.

The second line of each test case contains the string named 'STR'.

Output format:

For each test case, return the head of the linked list with updated character nodes after removing occurrences of the string.

Note:

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
0 <= N <= 10^3  
0 <= K <= 10^2

Where 'N' is the size of the singly linked list and 'K' is the size of the string.

Time limit: 1 sec

Sample Input 1 :

2
abcbcaab
bca
ny
nytq

Sample Output 1 :

a b 
n y

Explanation of The Sample Output 1:

In test case 1, after 1st removal of the string from the linked list: abcbcaab -> abcab. Now again, after 2nd removal of the string from the linked list: abcab -> ab. Thus ab is the updated linked list.

In test case 2, no occurrence of the string is present in the linked list, thus the linked list will be unchanged.

Sample Input 2 :

1
qcacca
cac
xxxxxxxxxxxxxx
xxx

Sample Output 2 :

q c a
x x

Explanation of The Sample Output 2 :

In test case 1, after the 1st removal of the string from the linked list: qcacca  ->  qca. Thus qca is the updated linked list.

In test case 2, as we can see there are total 4 occurrences of xxx, and by removing each occurrence: xxxxxxxxxxxxxx -> xxxxxxxxxxx -> xxxxxxxx -> xxxxx -> xx. Thus no more occurrence of the string is possible and hence the updated linked list will be xx.

Hint 1

Try using backtracking and recursion approach to find

the occurrence of a string in the linked list from the end.

Approaches (1)

Approach 1

Remove String

Starting from the head of the linked list make recursive calls until you reach the end of a linked list. Store the address of the head of the linked list in a pointer. Now you reach the end of the linked list and while backtracking, try to match the corresponding character of the string with the data stored in the current pointer ‘TEMP’ in linked list char by char.

If found then simply return the current pointer ‘TEMP’ of the updated linked list, else return the head of the linked list itself.

Time Complexity

O(N * K), where 'N' is the total length of the linked list and 'K' is the length of the string.

Since a number of recursive calls made is N in O(N) time and for each recursive call while backtracking, we are checking the string occurrence in the linked list in O(K) time. Thus the overall time complexity will be O(N * K).

Space Complexity

O(N), where 'N' is the total length of the linked list

Since a stack of size N is created during recursive calls and thus space complexity will be O(N).

(100% EXP penalty)

Remove String

Console