Sorting opens the way

Sorting is perhaps a very intuitive and easy ways to do certain stuff, that we might as well consider them as one of the legitimate pattern to solve a problem. There are two notable (string related) questions that I encountered in which we can go about solving the problem using sort. 

 

Here's how string can be sorted (just in case you aren't familiar with it)

import java.util.Arrays;

public class SortPattern {
    public static void main(String[] args) {
        String s = "dcba";
        // sort cannot be used like Arrays.sort(s), because Arrays.sort()
        // only takes in array as an argument, and string is not an array
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        System.out.println(charArray);
    }
}

 

 

Now, these are questions that I saw for which you can use sorting to intuitively solve the question.

 

1. Unique string detection: check if a given string is made up of unique characters (eg "abcd" is, and "abbcdd" isn't)

2. Permutation detection: check if a string is permutation of the other

 

public class SortPattern {
    public static void main(String[] args) {
        System.out.println(isUniqueCharacter("helloooo"));
        System.out.println(isPerm("abababab","aaaabbbb"));
    }


    public static boolean isUniqueCharacter(String str){
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        if(str == null || str.equals("")){
            return false;
        }

        char prevChar = charArray[0];
        for(int i = 1; i<charArray.length; i++){
            char curr = charArray[i];
            if(prevChar == curr){
                return false;
            }
            prevChar = curr;
        }
        return true;
    }

    public static boolean isPerm(String s, String t){
        if(s.length() != t.length()) return false;

        char[] charArray1 = s.toCharArray();
        char[] charArray2 = t.toCharArray();
        Arrays.sort(charArray1);
        Arrays.sort(charArray2);
        for(int i = 0; i<s.length(); i++){
            if(charArray1[i] != charArray2[i]){
                return false;
            }
        }
        return true;
    }
}

Again, note that these are by no means optimal, as sorting introduces default time complexity of O(nlogn). There are much better one pass solutions.