compare strings lexicographically in multiple queries

Question

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.

juvian · Accepted Answer · 2018-05-05 20:26:13Z

2

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

edited May 5, 2018 at 20:26

answered May 5, 2018 at 20:02

juvian

16.1k2 gold badges42 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

David Eisenstat Over a year ago

In theory a van Emde Boas tree can be used to reduce the complexity to O(Q log log N). In practice, the constants matter a lot.

juvian Over a year ago

@DavidEisenstat interesting structure, did not know about it. Might be worth it were a real problem and not an online one

Collectives™ on Stack Overflow

compare strings lexicographically in multiple queries

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related