CareerCup

p = 'abc'
q = 'cba'

'case 1: if a never repeats eg: abca so a can come after c but before b. so then i have to sort it'
sort_letter = {}


def find_precedence(str):
    for i in range(len(str)):
        sort_letter[str[i]] = str[i+1:]
    print(sort_letter)

def check_order(q,sort_letter):
    correct =  0
    for i in range(len(q)):
        if q[i] in sort_letter:
            print("checking - ",q[i]," ",sort_letter[q[i]]," ", q[i+1:])
            if sort_letter[q[i]] in q[i+1:] or  q[i+1:] in sort_letter[q[i]] :
                correct =1
            if q[i+1:] =='' and sort_letter[q[i]]:
                correct = 0
    print(correct)


find_precedence(p)
check_order(q,sort_letter)

Can a queue with hashmap of counts (to check if there's precendence constraint) work in this case? What do you think?

const isOrdered = (order, str) => {
	const orderRank = order.split("");
	let lastSeen = -1;

	return str.split("").reduce((accum, val) => {
		if (!accum) {
			return accum;
		}
		const lookUp = orderRank.indexOf(val),
			isOrdered = (lastSeen <= lookUp) || lookUp === -1;
		lastSeen = lookUp;
		return isOrdered;	
	});
};

Have a HashSet that stores the priority (ordering) of the string "abc"
Loop through characters of the given string, for each character check the priority
If the priority is not present OR if priority is same, go to the next character
Else If the priority is greater, increase the current_seen priority and go to the next character
Else return false

If reached end of string, return true

Check

Time complexity: O(n + m)
Space complexity: O(1), assuming both strings are ASCII

public static boolean checkOrder(String pattern, String str) {
    int[] label = new int[128];
    int order = 1;
    for (char c : pattern.toCharArray()) {
        label[c] = order;
        order++;
    }

    int lastOrder = -1;
    for (char c : str.toCharArray()) {
        int currOrder = label[c];
        if (currOrder == 0) continue;
        if (lastOrder != -1 && currOrder < lastOrder) return false;
        lastOrder = currOrder;
    }
    return true;
}