CareerCup

I think the question is more about generating all the possible well ordered strings rather than a boolean check of if a given string is well ordered or not. Correct me if I am wrong. My answer:

public class WellOrdered {

	private static int stringCount=0;
	private static void getWellOrderedString(String currentString,int charsLeft)
	{
		if(charsLeft==0)
		{
			System.out.println(currentString);
			stringCount++;
		}
		char i;
		if(currentString.isEmpty()) i='a';
		else
			i=(char) (currentString.charAt(currentString.length()-1)+1);
		for (;i<='z';i++)
		{
			getWellOrderedString(currentString+i, charsLeft-1);
		}
	}
	public static void main(String args[])
	{
		getWellOrderedString_Intf(3);
		System.out.println("Total count: "+stringCount);
	}
	private static void getWellOrderedString_Intf(int i) {
		getWellOrderedString("",i);
		
	}
}

Have an array of 26 characters with all the alphabets, or probably a hash table - index from 0-25.
Convert the string to character array.
Three variables - start index, end index, and tempindex.
Check character by character from the beginning of the string
At the very beginning of the string - set the startindex and endindex to 0 and tempindex to the index value of the first character.
as you go to the proceeding characters, check if that character's index value is greater than the tempindex, if yes - store that character's index in the tempindex, and that character's position in the string in the endindex.
this is repeated until the condition is false, wherein, the set of characters from startindex to endindex is printed, and the process is done again.

I think this could be done in O(n) time.

import java.util.ArrayList;


public class OrderedStrings {
	static ArrayList<Character> charArray = new ArrayList<>();
	public static void main(String args[]){
		int length =3;
		//if length = 1 (52 words) //assuming uppercase and lowercase
		// if length = 2, ab, aB,aC ... aZ, bc, bC ...// 2*50+2*48+...2*2=1300// assuming that we don't have same letters
		// if length = 3, abd, abD, abe, // 20800
		ArrayList<String> stringArray = new ArrayList<>();
		
		orderedStrings("",length,stringArray);
		
		
		System.out.println(stringArray);
		System.out.println("count:"+stringArray.size());
		
		
	}
	
	
	public static void orderedStrings(String currentString, int length, ArrayList<String> stringArray){
		String newString = currentString;
		if (length==0){
			stringArray.add(currentString);
		}
		else if(length>52){ // should be less than the number of all letters doubled (uppercase/lowercase)
			System.out.println("error: position can't be bigger than 52");
		}
		else {
			
			int nextChar = 'a';
			if (currentString.length()>0 ){
				int lastChar = currentString.charAt(currentString.length()-1);
				if (Character.isLowerCase(lastChar)){
					nextChar = lastChar + 1;
				}
				else if (Character.isUpperCase(lastChar)){
					nextChar = Character.toLowerCase(lastChar) + 1;
				}
			}
			for (int i=nextChar; i<='z'; i++){
				char toInsert = (char)i;
				if (Character.isLetter(toInsert)){ //is letter
					orderedStrings(currentString+toInsert, length-1, stringArray); //add the lower case char
					orderedStrings(currentString+Character.toUpperCase(toInsert), length-1, stringArray); //add the upper case char
				}
			}
		}
		
		
		
	}
}

public class Solution {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String a = "aBIY";
		String b = "bAiY";
		System.out.println(wellOrder(a));
		System.out.println(wellOrder(b));
	}
	public static boolean wellOrder(String s){
		String s1 = s.toLowerCase();
		for(int i=0;i<s1.length()-1;i++){
			if(s1.charAt(i)>s1.charAt(i+1)){
				return false;
			}
		}
		return true;
	}

}

public class Q7 {
	static int count;
	
	public static void main(String args[])
	{
		permute(2,"",'a');
		System.out.println(count);
	}

	private static void permute(int len, String string,char j) {
		char i;
		if(len==0)
		{
			System.out.println(string);
			count++;
			return;
		}
		for(i=j;i<='z';i++)
		{
			permute(len-1,string+i,(char) (i+1));
		}
		
		
	}

}

import java.util.HashMap;

import Util.populateHashMapABC;

public class WellOrderedString {

	public static void main(String  args[]){

		System.out.println(" wellOrderedString " + wellOrderedString("baisy"));
		
		System.out.println(" duplicateWellOrderedString " +  duplicateWellOrderedString("baisy"));
	}

	private static Boolean wellOrderedString(String sample) {

		try{
			boolean isWellOrdered =  false;

			HashMap< String, Integer> hashMap = new HashMap<String, Integer>();
			hashMap = populateHashMapABC.populateHashMap(hashMap);

			char[] characterArray = sample.toCharArray();
			int tempCharacter = hashMap.get(String.valueOf(characterArray[0]));
			
			int lowerCharacter = 0;

			for(int i=1; i < characterArray.length; i++){
				lowerCharacter = tempCharacter;
				tempCharacter =  hashMap.get(String.valueOf(characterArray[i]));
			
				if(lowerCharacter > tempCharacter){
					return false;
				}

			}

			isWellOrdered = true;

			return isWellOrdered; 
		}catch(Exception e){
			e.printStackTrace();
			return false;
		}finally{

		}

	}
	
	private static Boolean duplicateWellOrderedString(String sample){
		
		try{
			boolean iswellOrdered =  true;
			
			HashMap< String, Integer> hashMap =  new HashMap<String, Integer>();
			hashMap = populateHashMapABC.populateHashMap(hashMap);
			
			char[] characterArray = sample.toCharArray();
			int tempChar = hashMap.get(String.valueOf(characterArray[0]));
			int lowerChar = 0;
			
			for(int i=1; i< characterArray.length; i++){
				lowerChar = tempChar;
				tempChar = hashMap.get(String.valueOf(characterArray[i]));
				if(lowerChar > tempChar){
					return false;
				}
			}
			return iswellOrdered;
		}catch (Exception e){
			e.printStackTrace();
			return false;
		}
	}

}

import java.util.ArrayList;

public class WellOrderedStrings
{
	public static ArrayList<String> getWellOrderedStrings(int length)
	{
		if (length > 26 * 2) // all lower case and upper case letters
			System.out.println("Error: length must be <= 52");

		// String of all alphabet
		String alphabet = "abcdefghijklmnobqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

		// List of all found sequences till now
		ArrayList<String> allSeqs = new ArrayList<String>();
		for (int i = alphabet.length() - 1; i >= 0; i--)
		{

			// List of new generated sequences
			ArrayList<String> newSeqs = new ArrayList<String>();

			// Add new sequences
			for (String seq : allSeqs)
			{

				// interested only in sequences <= length
				if (seq.length() <= length - 1)
					newSeqs.add(alphabet.charAt(i) + seq);
			}
			allSeqs.addAll(newSeqs);
			allSeqs.add(alphabet.charAt(i) + "");
		}

		// List of final results
		ArrayList<String> finalResult = new ArrayList<String>();

		for (String seq : allSeqs)
		{
			if (seq.length() == length)
			{
				finalResult.add(seq);
			}
		}

		// Print size of final list
		System.out.println(finalResult.size());

		return finalResult;
	}

	public static void main(String args[])
	{
		getWellOrderedStrings(4);
	}
}

package my.practise.dynamicprogramming;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class WellOrderedStrings {
	private static final String s = "abcdefghijklmnobqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	private static HashMap<String, List<String>> cache = new HashMap<String, List<String>>();

	public static List<String> getWellOrderedStrings(int length, int start,
			int end) {
		if (cache.containsKey(length + ":" + start + ":" + end)) {
			return cache.get(length + ":" + start + ":" + end);
		} else {
			List<String> list = new ArrayList<String>();

			if (end - start == length && length != 0 && end > start) {
				list.add(s.substring(start, end));
			}

			else if (!(length < 0) && (length < end - start)) {
				list.addAll(getWellOrderedStrings(length, start + 1, end));
				char c = s.charAt(start);
				List<String> subList = getWellOrderedStrings(length - 1,
						start + 1, end);
				for (String str : subList) {
					list.add(c + str);
				}
			}
			cache.put(length+":"+start+":"+end, list);
			return list;
		}
	}

	public static void main(String args[]) {
		System.out.println(getWellOrderedStrings(5, 0, s.length()));
	}

}

Should we consider 'a' is in front of 'A'? Or they are not considered as different in order?

I think this is a simple solution to the problem

public static void orderedStr(String[] str){
		int flag = 0;
		for(int j=0;j<str.length;j++){
			String temp = str[j].toLowerCase();
		for(int i = 0;i < str[j].length()-1;i++)
		{	
			if((temp.charAt(i) <=temp.charAt(i+1))){
				flag = 1;
			}
			else{
				flag = 0;
				break;
			}
		}//i-for
		if(flag == 1)
			System.out.println(str[j]);
		}
	}// j-for

I think this is a simple solution to the problem

public static void orderedStr(String[] str){
		int flag = 0;
		for(int j=0;j<str.length;j++){
			String temp = str[j].toLowerCase();
		for(int i = 0;i < str[j].length()-1;i++)
		{	
			if((temp.charAt(i) <=temp.charAt(i+1))){
				flag = 1;
			}
			else{
				flag = 0;
				break;
			}
		}//i-for
		if(flag == 1)
			System.out.println(str[j]);
		}
	}// j-for

I think this is a simple solution to the problem

public static void orderedStr(String[] str){
		int flag = 0;
		for(int j=0;j<str.length;j++){
			String temp = str[j].toLowerCase();
		for(int i = 0;i < str[j].length()-1;i++)
		{	
			if((temp.charAt(i) <=temp.charAt(i+1))){
				flag = 1;
			}
			else{
				flag = 0;
				break;
			}
		}//i-for
		if(flag == 1)
			System.out.println(str[j]);
		}
	}// j-for

Pythonic Solution

def backTrack_solve(arr,index,result,limit):
    if(len(result)==limit):
        print result
    else:
        for i in xrange(index,len(arr)):
            result.append(arr[i])
            backTrack_solve(arr,i+1,result,limit)
            result.remove(arr[i])



if __name__ == "__main__":
    limit = int(raw_input())
    result = list()
    arr_w = list()
    for x in range(97,123):
        arr_w.append(chr(x))
    backTrack_solve(arr_w,0,result,limit)

import java.util.*;

public class WellOrderedStrings {
	
	static void findPossible (String s,int index,int k,List<String> l)
	{
		if (index==0) {l.add(s);return;}
		for (int i=k;i<26;i++)
		{
			findPossible(s+((char)('a'+i)),index-1,i+1,l);
			findPossible(s+((char)('A'+i)),index-1,i+1,l);
		}
	}

    public static void main(String[] args) {
	int n=2;
	List<String> l = new ArrayList<String>();
	findPossible("",n,0,l);
	System.out.println("Total of:" + l.size());
	System.out.println(l);
    }
}

public static List<String> generateAllWellOrderedString(int length) {
List<String> result = new ArrayList<String>();
if(length == 0) {
return result;
}
ArrayList<Character> characterSet = new ArrayList<Character>();
for(char c = 'a'; c <= 'z'; c++) {
characterSet.add(c);
}
for(char c = 'A'; c <= 'Z'; c++) {
characterSet.add(c);
}
for(int i = 0; i < characterSet.size(); i++) {
String prefix = Character.toString(characterSet.get(i));
result.addAll(getWellOrderedString(prefix, length - 1, characterSet));
}
return result;
}

private static List<String> getWellOrderedString(String prefix, int lengthRemaining, ArrayList<Character> characterSet) {
List<String> result = new ArrayList<String>();
if(lengthRemaining == 0) {
result.add(prefix);
return result;
}
char currentEnd = prefix.charAt(prefix.length() - 1);
for(int i = characterSet.indexOf(currentEnd) + 1; i < characterSet.size(); i++) {
String newPrefix = prefix + characterSet.get(i);
result.addAll(getWellOrderedString(newPrefix, lengthRemaining - 1, characterSet));
}
return result;
}

private static void testGenerateAllWellOrderedString() {
System.out.println("\nTest Generate All Well Ordered String:");

System.out.println("For length 1:");
List<String> result1 = generateAllWellOrderedString(1);
System.out.println(result1.size() + "\n" + result1);

System.out.println("For length 2:");
List<String> result2 = generateAllWellOrderedString(2);
System.out.println(result2.size() + "\n" + result2);

System.out.println("For length 3:");
List<String> result3 = generateAllWellOrderedString(3);
System.out.println(result3.size() + "\n");
}

public static List<String> generateAllWellOrderedString(int length) {
		List<String> result = new ArrayList<String>();
		if(length == 0) {
			return result;
		}
		ArrayList<Character> characterSet = new ArrayList<Character>();
		for(char c = 'a'; c <= 'z'; c++) {
			characterSet.add(c);
		}
		for(char c = 'A'; c <= 'Z'; c++) {
			characterSet.add(c);
		}
		for(int i = 0; i < characterSet.size(); i++) {
			String prefix = Character.toString(characterSet.get(i));
			result.addAll(getWellOrderedString(prefix, length - 1, characterSet));
		}
		return result;
	}
	
	private static List<String> getWellOrderedString(String prefix, int lengthRemaining, ArrayList<Character> characterSet) {
		List<String> result = new ArrayList<String>();
		if(lengthRemaining == 0) {
			result.add(prefix);
			return result;
		}
		char currentEnd = prefix.charAt(prefix.length() - 1);
		for(int i = characterSet.indexOf(currentEnd) + 1; i < characterSet.size(); i++) {
			String newPrefix = prefix + characterSet.get(i);
			result.addAll(getWellOrderedString(newPrefix, lengthRemaining - 1, characterSet));
		}
		return result;
	}
	
	private static void testGenerateAllWellOrderedString() {
		System.out.println("\nTest Generate All Well Ordered String:");
		
		System.out.println("For length 1:");
		List<String> result1 = generateAllWellOrderedString(1);
		System.out.println(result1.size() + "\n" + result1);
		
		System.out.println("For length 2:");
		List<String> result2 = generateAllWellOrderedString(2);
		System.out.println(result2.size() + "\n" + result2);
		
		System.out.println("For length 3:");
		List<String> result3 = generateAllWellOrderedString(3);
		System.out.println(result3.size() + "\n");
	}