Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1061.html

1061. Lexicographically Smallest Equivalent String

Level

Medium

Description

Given strings A and B of the same length, we say A[i] and B[i] are equivalent characters. For example, if A = "abc" and B = "cde", then we have 'a' == 'c', 'b' == 'd', 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

  • Reflexivity: ‘a’ == ‘a’
  • Symmetry: ‘a’ == ‘b’ implies ‘b’ == ‘a’
  • Transitivity: ‘a’ == ‘b’ and ‘b’ == ‘c’ implies ‘a’ == ‘c’

For example, given the equivalency information from A and B above, S = "eed", "acd", and "aab" are equivalent strings, and "aab" is the lexicographically smallest equivalent string of S.

Return the lexicographically smallest equivalent string of S by using the equivalency information from A and B.

Example 1:

Input: A = “parker”, B = “morris”, S = “parser”

Output: “makkek”

Explanation: Based on the equivalency information in A and B, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is “makkek”.

Example 2:

Input: A = “hello”, B = “world”, S = “hold”

Output: “hdld”

Explanation: Based on the equivalency information in A and B, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter ‘o’ in S is changed to ‘d’, the answer is “hdld”.

Example 3:

*Input: A = “leetcode”, B = “programs”, S = “sourcecode”

Output: “aauaaaaada”

Explanation: We group the equivalent characters in A and B as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in S except ‘u’ and ‘d’ are transformed to ‘a’, the answer is “aauaaaaada”.

Note:

  1. String A, B and S consist of only lowercase English letters from 'a' - 'z'.
  2. The lengths of string A, B and S are between 1 and 1000.
  3. String A and B are of the same length.

Solution

Use two maps to store each letter with its group and each group with the letters in the group, respectively. Initially, all letters have different groups, and each group has only one letter, which is the letter itself.

Loop over A and B and merge each pair of letters into one group. When merging into one group, only remain the group that is lexicographically smallest. All the letters from both previous groups are mapped to the remaining group, and the remaining group is mapped to all the letters from both previous groups.

After the mappings are done, loop over S and obtain the group for each letter and replace the letter in S. Finally, return the new string.

  • class Solution {
    public String smallestEquivalentString(String A, String B, String S) {
        Map<Character, Character> letterGroupMap = new HashMap<Character, Character>();
        Map<Character, Set<Character>> groupLettersMap = new HashMap<Character, Set<Character>>();
        for (char c = 'a'; c <= 'z'; c++) {
            letterGroupMap.put(c, c);
            Set<Character> set = new HashSet<Character>();
            set.add(c);
            groupLettersMap.put(c, set);
        }
        int length = A.length();
        for (int i = 0; i < length; i++) {
            char c1 = A.charAt(i), c2 = B.charAt(i);
            char group1 = letterGroupMap.get(c1), group2 = letterGroupMap.get(c2);
            if (group1 != group2) {
                Set<Character> set1 = groupLettersMap.get(group1);
                Set<Character> set2 = groupLettersMap.get(group2);
                if (group1 < group2) {
                    for (char c : set2)
                        letterGroupMap.put(c, group1);
                    set1.addAll(set2);
                    groupLettersMap.put(group1, set1);
                    groupLettersMap.remove(group2);
                } else {
                    for (char c : set1)
                        letterGroupMap.put(c, group2);
                    set2.addAll(set1);
                    groupLettersMap.put(group2, set2);
                    groupLettersMap.remove(group1);
                }
            }
        }
        char[] array = S.toCharArray();
        int strLength = array.length;
        for (int i = 0; i < strLength; i++) {
            char c = array[i];
            char group = letterGroupMap.get(c);
            array[i] = group;
        }
        return new String(array);
    }
}

  • class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        p = list(range(26))

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        for i in range(len(s1)):
            a, b = ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')
            pa, pb = find(a), find(b)
            if pa < pb:
                p[pb] = pa
            else:
                p[pa] = pb

        res = []
        for a in baseStr:
            a = ord(a) - ord('a')
            res.append(chr(find(a) + ord('a')))
        return ''.join(res)



  • class Solution {
public:
    vector<int> p;

    string smallestEquivalentString(string s1, string s2, string baseStr) {
        p.resize(26);
        for (int i = 0; i < 26; ++i)
            p[i] = i;
        for (int i = 0; i < s1.size(); ++i) {
            int a = s1[i] - 'a', b = s2[i] - 'a';
            int pa = find(a), pb = find(b);
            if (pa < pb)
                p[pb] = pa;
            else
                p[pa] = pb;
        }
        string res = "";
        for (char a : baseStr) {
            char b = (char) (find(a - 'a') + 'a');
            res += b;
        }
        return res;
    }

    int find(int x) {
        if (p[x] != x)
            p[x] = find(p[x]);
        return p[x];
    }
};

  • var p []int

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
	p = make([]int, 26)
	for i := 0; i < 26; i++ {
		p[i] = i
	}
	for i := 0; i < len(s1); i++ {
		a, b := int(s1[i]-'a'), int(s2[i]-'a')
		pa, pb := find(a), find(b)
		if pa < pb {
			p[pb] = pa
		} else {
			p[pa] = pb
		}
	}
	var res []byte
	for _, a := range baseStr {
		b := byte(find(int(a-'a'))) + 'a'
		res = append(res, b)
	}
	return string(res)
}

func find(x int) int {
	if p[x] != x {
		p[x] = find(p[x])
	}
	return p[x]
}

All Problems

All Solutions