Finding the leftmost critical factorization on unordered alphabet

• We consider algorithms computing the leftmost critical point on unordered alphabets.
• We describe an O(nlogn)-time algorithm finding the leftmost critical point.
• We investigate some combinatorial properties of strings related to our problem.
• Using found combinatorial facts, we improve our first algorithm to O(n)O(n) algorithm.

We present a linear time and space algorithm computing the leftmost critical factorization of a given string on an unordered alphabet.