CODEWITHSUNDEEP
stringalgorithmdata-structures
prashantgpt91
prashantgpt91

Reputation: 1795

compare strings lexicographically in multiple queries

Compare two numbers in the form of string lexicographically multiple times.

What I tried

the question is straight forward, to compare string after change but I am getting Time limit exceeded error because of multiple queries.

I was searching internet and came across segment tree to solve range queries. But alas I am not able to visualise, how it can help here.

Any hint is appreciated.

Upvotes: 0

Views: 154

Answers (1)

juvian
juvian

Reputation: 16068

Segment tree seems overkill for this problem. When will B be lexicographically larger than A? When at index i, A[i] = 0, B [i] = 1 and A[0:i] = B [0:i]. Iterate over both strings at same time and keep in a set all indexes where they are different.

For each query at index i, update B to 1. Then check if B[i] = A[i]. IF they are equal, erase i from the indexes set. Otherwise, add it to the set. If there is no index left in the set, A and B are now equal => answer YES.

If there is at least 1 element, get the lowest index. If this index is j, that means A[0:j] = B[0:j] but A[j] != B[j]. So either A is 0 and B is 1 or A is 1 and B is 0. Depending on that, answer YES or NO.

This has complexity of O(Q log N), being Q the amount of queries

Upvotes: 2

Related Questions