-1

I have a string and I want to get the order relationship between string elements in linear time.

For example, the string "abc", there are three partial order relations, namely ab, bc, ac

4
  • Do I understand you correctly? You want to generate all 2-grams and order those 2-grams alphabetically
    – Turing85
    Sep 19, 2020 at 6:35
  • Sorry, maybe I didn't express it clearly. I want to get all the partial order relations. For example, the string "abc", there are three partial order relations, namely ab, bc, ac
    – Jhon Lee
    Sep 19, 2020 at 6:40
  • Ah okay. There might be a problem with the linear time complexity requirement. I would argue that it is inot possible since odering has time complexity n log(n). But one could also argue that the set of 2-letter words is of constant size, thus the list of partial order is of at most this constant size and thus complexity recudes to O(c).
    – Turing85
    Sep 19, 2020 at 6:44

1 Answer 1

0

If you want to generate all the ordered pairs - well there are n^2 of those, so you won't even be able to print them in linear time.

However, if you just need to be able to lookup the ordering of two characters for some larger algorithm (and they are all unique in the original string): You could build a map of characters to their index in the string in a single pass (linear time). Then, whenever you need to know the ordering of a given pair, look up and compare their indices in constant time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.