1239.Β Maximum Length of a Concatenated String with Unique Characters

  • μ£Όμ–΄μ§„ λ¬Έμžμ—΄ λ°°μ—΄ arr 의 λΆ€λΆ„ λ°°μ—΄ arr’에 λŒ€ν•΄μ„œ λͺ¨λ“  λ¬Έμžμ—΄μ„ μ΄μ–΄λΆ™μ˜€μ„ λ•Œ μ€‘λ³΅λ˜λŠ” κΈ€μžκ°€ μ—†λŠ” λΆ€λΆ„ λ°°μ—΄μ˜ μ΅œλŒ€ 길이λ₯Ό κ΅¬ν•˜λŠ” 문제.
    • λΆ€λΆ„ 배열은 전체 λ°°μ—΄μ—μ„œ μž„μ˜μ˜ 개수의 μ›μ†Œλ₯Ό μ œκ±°ν–ˆμ„ λ•Œ λ§Œλ“€μ–΄μ§€λŠ” 배열을 λ§ν•œλ‹€.
  • κ²°κ΅­ λͺ¨λ“  λΆ€λΆ„ 배열에 λŒ€ν•΄μ„œ 이어뢙인 λ¬Έμžμ—΄μ— μ€‘λ³΅λœ κΈ€μžκ°€ μ—†λŠ”μ§€ ν™•μΈν•˜λ©΄ λ˜λŠ” λ¬Έμ œμ΄λ‹€.
  • λ¬Έμžμ—΄ 배열에 μ†ν•œ 각 λ¬Έμžλ³„λ‘œ μΆœν˜„ μ—¬λΆ€λ₯Ό λ§ˆν‚Ήν•œλ‹€.
    • λ¬Έμžμ—΄μ€ μ˜μ–΄ μ†Œλ¬Έμžλ‘œλ§Œ κ΅¬μ„±λ˜μ–΄μžˆμœΌλ―€λ‘œ μΆœν˜„ μ—¬λΆ€λ₯Ό Integer의 0 ~ 25 번째 bit에 λ§ˆν‚Ήν•  수 μžˆλ‹€.
    • λ§Œμ•½ ν•˜λ‚˜μ˜ λ¬Έμžμ—΄ 내에 이미 쀑볡이 μžˆλ‹€λ©΄ -1을 λŒλ €μ€€λ‹€ (λͺ¨λ“  bitκ°€ λ§ˆν‚Ήλ¨).
  • λ¬Έμžμ—΄ 배열을 μˆœμ„œλŒ€λ‘œ λ”°λΌκ°€λ©΄μ„œ λ‹€μŒ 사항을 ν™•μΈν•œλ‹€.
    • ν˜„μž¬ μœ„μΉ˜ indexλ₯Ό κΈ°μ€€μœΌλ‘œ,
    • (1) ν˜„μž¬ λ¬Έμžμ—΄μ„ λΆ€λΆ„ 배열에 ν¬ν•¨μ‹œν‚€μ§€ μ•Šμ€ 경우 이어뢙인 λ¬Έμžμ—΄μ˜ 길이λ₯Ό κ΅¬ν•œλ‹€.
    • (2) ν˜„μž¬ λ¬Έμžμ—΄μ„ λΆ€λΆ„ 배열에 ν¬ν•¨μ‹œν‚¨ 경우 이어뢙인 λ¬Έμžμ—΄μ˜ 길이λ₯Ό κ΅¬ν•œλ‹€. 단, ν˜„μž¬ λ¬Έμžμ—΄μ„ ν¬ν•¨μ‹œμΌ°μ„ λ•Œ 문자 쀑볡이 λ°œμƒν•˜λŠ”μ§€ ν™•μΈν•œλ‹€.
      • 문자의 μΆœν˜„ μ—¬λΆ€λ₯Ό bit둜 λ§ˆν‚Ήν•˜μ˜€μœΌλ―€λ‘œ ν˜„μž¬κΉŒμ§€ λˆ„μ λœ λ¬Έμžμ—΄μ˜ μΆœν˜„ μ—¬λΆ€ λ§ˆν‚Ή κ°’ currκ³Ό ν˜„μž¬ λ¬Έμžμ—΄μ˜ λ§ˆν‚Ή κ°’ bits[index] 을 logical and &μ—°μ‚°ν•˜μ—¬ 값이 0이 μ•„λ‹ˆλΌλ©΄ 쀑볡이 λ°œμƒν•œ κ²ƒμœΌλ‘œ λ³Ό 수 μžˆλ‹€.
      • 쀑볡이 λ°œμƒν–ˆλ‹€λ©΄ ν•΄λ‹Ή λΆ€λΆ„ λ°°μ—΄μ˜ 경우 κ²°κ³Ό κ°’μ—μ„œ μ œμ™Έν•΄μ•Ό ν•œλ‹€.
    • 두 κ°’ 쀑 길이가 κΈ΄ 것을 λ‹΅μœΌλ‘œ ν•œλ‹€.
class Solution { int countBits(String s) { int result = 0; for (int i = 0; i < s.length(); ++i) { int bit = 1 << (s.charAt(i) - 'a'); if ((result & bit) != 0) return -1; result |= bit; } return result; } int traverse(List<String> arr, int[] bits, int index, int curr) { if (index >= bits.length) return 0; int count = traverse(arr, bits, index + 1, curr); if (bits[index] != -1 && (curr & bits[index]) == 0) { count = Math.max(count, traverse(arr, bits, index + 1, curr | bits[index]) + arr.get(index).length()); } return count; } public int maxLength(List<String> arr) { int[] bits = new int[arr.size()]; for (int i = 0; i < arr.size(); ++i) { bits[i] = countBits(arr.get(i)); } return traverse(arr, bits, 0, 0); } }