Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## 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;

for (int i = 1; i < str2.length(); i++)
{
{
// New lexicographical minimum found.
// Reset all parameters here.
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.
offset = 0;
}
else
{
// In the new match, some character is found which is higher
// than the character at same offset in the previous answer.
offset = 0;
}

// Debug prints
System.out.println ("-------------------------");
System.out.println (getSpace(i)+"i");
System.out.println (str2);
if (offset > 0)
System.out.println (getSpace(i-offset+1) + str2.substring(i-offset+1, i+1));
System.out.println ();
}

}

{
String s = "";
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: