Lexicographical minimum in a String

Table of Contents

Lexicographical minimum in a String

Problem: Given a string, find the lexicographical minimum string keeping the order of alphabets same as the original string.

For example:

Given String	Lexicographical Minimum
DABC	ABCD
ABCD	ABCD
CABABC	ABABCC
ABABCABA	ABAABABC

Solution: This can be done in O(n) by the following code:

Code:


public class LexicographicalMinimumString 
{

    public static void main(String[] args) 
    {
        String [] testStrings = {"ABCD", "ACACAB", "CABABC", "ABABCABA", "AAA"};
        for (String s : testStrings)
        {
            System.out.println ("\n\n=========================");
            System.out.println ("Input: " + s);
            System.out.println (s + ": " + lexMin(s));
        }
    }


    static String lexMin(String str) 
    { 
        String str2 = str + str; 

        int offset = 0; 
        int answer = 0; 

        for (int i = 1; i < str2.length(); i++) 
        { 
            if (str2.charAt(i) < str2.charAt(answer)) 
            { 
                // New lexicographical minimum found.
                // Reset all parameters here.
                answer = i; 
                offset = 0; 
            } 
            else if (str2.charAt(i) == str2.charAt(answer + offset)) 
            { 
                // Keep moving the offset till this new string matches the previous answer
                offset++; 
            } 
            else if (str2.charAt(i) < str2.charAt(answer + offset)) 
            { 
                // In the new match, some character is found which is lower 
                // than the character at same offset in the previous answer.
                // So new answer becomes the lexicographical minimum, discard 
                // the previous answer in favor of the new answer.
                answer = i - offset; 
                offset = 0; 
                i = answer;
            } 
            else 
            { 
                // In the new match, some character is found which is higher 
                // than the character at same offset in the previous answer.
                // So new answer cannot be the lexicographical minimum, discard it.
                offset = 0; 
            }
            
            // Debug prints
            System.out.println ("-------------------------");
            System.out.println ("i="+i + ", answer=" + answer + ", offset="+offset);
            System.out.println (getSpace(i)+"i");
            System.out.println (str2);
            System.out.println (getSpace(answer) + str2.substring(answer, answer+str.length()));
            if (offset > 0)
                System.out.println (getSpace(i-offset+1) + str2.substring(i-offset+1, i+1));
            System.out.println ();
        } 

        return str2.substring(answer, answer+str.length()); 

    }


    static String getSpace(int answer) 
    {
        String s = "";
        while (answer-- > 0)
            s += " ";
        return s;
    }

}

Sample Execution:

=========================
Input: ABCD
-------------------------
i=1, answer=0, offset=0
 i
ABCDABCD
ABCD

-------------------------
i=2, answer=0, offset=0
  i
ABCDABCD
ABCD

-------------------------
i=3, answer=0, offset=0
   i
ABCDABCD
ABCD

-------------------------
i=4, answer=0, offset=1
    i
ABCDABCD
ABCD
    A

-------------------------
i=5, answer=0, offset=2
     i
ABCDABCD
ABCD
    AB

-------------------------
i=6, answer=0, offset=3
      i
ABCDABCD
ABCD
    ABC

-------------------------
i=7, answer=0, offset=4
       i
ABCDABCD
ABCD
    ABCD

ABCD: ABCD

=========================
Input: ACACAB
-------------------------
i=1, answer=0, offset=0
 i
ACACABACACAB
ACACAB

-------------------------
i=2, answer=0, offset=1
  i
ACACABACACAB
ACACAB
  A

-------------------------
i=3, answer=0, offset=2
   i
ACACABACACAB
ACACAB
  AC

-------------------------
i=4, answer=0, offset=3
    i
ACACABACACAB
ACACAB
  ACA

-------------------------
i=2, answer=2, offset=0
  i
ACACABACACAB
  ACABAC

-------------------------
i=3, answer=2, offset=0
   i
ACACABACACAB
  ACABAC

-------------------------
i=4, answer=2, offset=1
    i
ACACABACACAB
  ACABAC
    A

-------------------------
i=4, answer=4, offset=0
    i
ACACABACACAB
    ABACAC

-------------------------
i=5, answer=4, offset=0
     i
ACACABACACAB
    ABACAC

-------------------------
i=6, answer=4, offset=1
      i
ACACABACACAB
    ABACAC
      A

-------------------------
i=7, answer=4, offset=0
       i
ACACABACACAB
    ABACAC

-------------------------
i=8, answer=4, offset=1
        i
ACACABACACAB
    ABACAC
        A

-------------------------
i=9, answer=4, offset=0
         i
ACACABACACAB
    ABACAC

-------------------------
i=10, answer=4, offset=1
          i
ACACABACACAB
    ABACAC
          A

-------------------------
i=11, answer=4, offset=2
           i
ACACABACACAB
    ABACAC
          AB

ACACAB: ABACAC

=========================
Input: CABABC
-------------------------
i=1, answer=1, offset=0
 i
CABABCCABABC
 ABABCC

-------------------------
i=2, answer=1, offset=0
  i
CABABCCABABC
 ABABCC

-------------------------
i=3, answer=1, offset=1
   i
CABABCCABABC
 ABABCC
   A

-------------------------
i=4, answer=1, offset=2
    i
CABABCCABABC
 ABABCC
   AB

-------------------------
i=5, answer=1, offset=0
     i
CABABCCABABC
 ABABCC

-------------------------
i=6, answer=1, offset=0
      i
CABABCCABABC
 ABABCC

-------------------------
i=7, answer=1, offset=1
       i
CABABCCABABC
 ABABCC
       A

-------------------------
i=8, answer=1, offset=2
        i
CABABCCABABC
 ABABCC
       AB

-------------------------
i=9, answer=1, offset=3
         i
CABABCCABABC
 ABABCC
       ABA

-------------------------
i=10, answer=1, offset=4
          i
CABABCCABABC
 ABABCC
       ABAB

-------------------------
i=11, answer=1, offset=5
           i
CABABCCABABC
 ABABCC
       ABABC

CABABC: ABABCC

=========================
Input: ABABCABA
-------------------------
i=1, answer=0, offset=0
 i
ABABCABAABABCABA
ABABCABA

-------------------------
i=2, answer=0, offset=1
  i
ABABCABAABABCABA
ABABCABA
  A

-------------------------
i=3, answer=0, offset=2
   i
ABABCABAABABCABA
ABABCABA
  AB

-------------------------
i=4, answer=0, offset=0
    i
ABABCABAABABCABA
ABABCABA

-------------------------
i=5, answer=0, offset=1
     i
ABABCABAABABCABA
ABABCABA
     A

-------------------------
i=6, answer=0, offset=2
      i
ABABCABAABABCABA
ABABCABA
     AB

-------------------------
i=7, answer=0, offset=3
       i
ABABCABAABABCABA
ABABCABA
     ABA

-------------------------
i=5, answer=5, offset=0
     i
ABABCABAABABCABA
     ABAABABC

-------------------------
i=6, answer=5, offset=0
      i
ABABCABAABABCABA
     ABAABABC

-------------------------
i=7, answer=5, offset=1
       i
ABABCABAABABCABA
     ABAABABC
       A

-------------------------
i=7, answer=7, offset=0
       i
ABABCABAABABCABA
       AABABCAB

-------------------------
i=8, answer=7, offset=1
        i
ABABCABAABABCABA
       AABABCAB
        A

-------------------------
i=9, answer=7, offset=0
         i
ABABCABAABABCABA
       AABABCAB

-------------------------
i=10, answer=7, offset=1
          i
ABABCABAABABCABA
       AABABCAB
          A

-------------------------
i=11, answer=7, offset=0
           i
ABABCABAABABCABA
       AABABCAB

-------------------------
i=12, answer=7, offset=0
            i
ABABCABAABABCABA
       AABABCAB

-------------------------
i=13, answer=7, offset=1
             i
ABABCABAABABCABA
       AABABCAB
             A

-------------------------
i=14, answer=7, offset=0
              i
ABABCABAABABCABA
       AABABCAB

-------------------------
i=15, answer=7, offset=1
               i
ABABCABAABABCABA
       AABABCAB
               A

ABABCABA: AABABCAB

=========================
Input: AAA
-------------------------
i=1, answer=0, offset=1
 i
AAAAAA
AAA
 A

-------------------------
i=2, answer=0, offset=2
  i
AAAAAA
AAA
 AA

-------------------------
i=3, answer=0, offset=3
   i
AAAAAA
AAA
 AAA

-------------------------
i=4, answer=0, offset=4
    i
AAAAAA
AAA
 AAAA

-------------------------
i=5, answer=0, offset=5
     i
AAAAAA
AAA
 AAAAA

AAA: AAA

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email:	(Your email is not shared with anybody)

Comment:

Facebook comments:

Site Owner: Sachin Goyal