본문으로 건너뛰기

1156 - Swap For Longest Repeated Character Substring

info

풀이 키워드​

스포주의

해시 투포인터


풀이 코드​

info
  • 메모리: 42710 KB
  • 시간: 3 ms
class Solution {
    static {
        for (int i=0; i < 100; ++i) maxRepOpt1("");
    }

    public static int maxRepOpt1(String text) {
        Map<Character, Integer> chMap = new HashMap<>(); // char counters
        char[] textArr = text.toCharArray();

        for (char ch : textArr) {
            chMap.merge(ch, 1, Integer::sum);
        }

        // calc 1-ignorance length
        int mxlen = 1; // if text.length == 1 then mxlen is 1
        int i = 0;
        int j = 1;
        while (i < textArr.length) {
            char targetCh = textArr[i];
            int len = 1;
            boolean skipped = false; // 1-ignored?
            j = i+1;
            int breakPoint = j;
            while (j < textArr.length) {
                if (textArr[j] == targetCh) ++j; // same
                else { // not same
                    if (!skipped) {
                        breakPoint = j;
                        skipped = true;
                        ++j;
                    }
                    else break;
                }
            }
            if (!skipped) breakPoint = j;

            // if not skipped then force extend (corner case)
            int extended = (skipped ? j-i : j-i+1);

            // if no spare character then -1
            int cand = (chMap.get(targetCh) < extended) ? extended-1 : extended;
            //System.out.println(textArr[i] + " " + chMap.get(targetCh) + " " + cand);

            mxlen = Math.max(mxlen, cand);
            i = breakPoint;
        }
        
        return mxlen;
    }
}

풀이 해설​

WIP


메모​

  • 난이도가 좀 있는게, 해시 좋아하는 카카오 공채 코테에서나 나올듯
  • 시간이 좀 걸렸고(1시간 반 정도), WA 받으면서 corner case 잡았지만 유형도 맞췄고 풀이 방향성은 매우 좋았음.
  • 가벼운 마음으로 코랜디 돌렸는데 처음부터 폭탄 잡았네 아