문자열

 

 

 

 

문자열 찾기 

 

1) longest-substring-without-repeating-characters

문제 : https://leetcode.com/problems/longest-substring-without-repeating-characters/

 

1. 슬라이딩 윈도우 

반복되지 않는 가장 긴 문자열의 길이를 반환하는 문제다. 

(풀고 보니 슬라이딩 윈도우와 비슷한 방식으로 풀었다.)

n = 문자열길이, k = 현재 윈도우 길이 (최대 n)이라고 가정할때, 

temp.contains(), temp.indexOf(), temp.substring(...) + s[i] 모두 O(k)의 시간복잡도를 갖고, 이 연산이 최대 n번 반복될 수 있다. 

시간복잡도 : O(n^2) 

문자열 연산이 계속 일어나므로 새로운 문자열이 계속 생성될 수 있다. 

공간복잡도 : O(n) 

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        if(s.length == 0 || s.length ==1) return s.length
        var temp = ""
        var answer = 0
        for(i in 0 until s.length) {
            if(temp.contains(s[i])) {
                answer = max(temp.length, answer)
                val idx = temp.indexOf(s[i])
                temp = temp.substring(idx +1) + s[i]
            } else {
                temp += s[i]
            }
        }
        return max(answer, temp.length) 
    }
}

 

 

2. 슬라이딩 윈도우 + HashSet 

HashMap (or Set) + Two Pointer로 O(n)의 풀이도 가능하다. 

 

각 문자는 최대 두번만 확인되므로 

시간복잡도 : O(n) 

문자 Set에 최대 n개를 저장하므로 

공간복잡도 : O(n)

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        val set = mutableSetOf<Char>()
        var left = 0 
        var right = 0
        var answer = 0 

        while (right < s.length) {
            if(set.contains(s[right]).not()) {
                set.add(s[right])
                answer = max(answer, right-left +1)
                right ++
            }else {
                set.remove(s[left])
                left ++
            }
        }
        return answer 
    }
}

 

 

 

2) longest-repeating-character-replacement

k개의 문자열을 대체했을때 가장 긴 중복 문자열의 길이를 찾는 문제다. 

문제 : https://leetcode.com/problems/longest-repeating-character-replacement

슬라이딩 윈도우를 하면서 문자열 내에서 교체 가능한 윈도우를 찾고, 그 길이를 측정하는 방식으로 진행할 수 있다. 

 

시간 복잡도 : O(n) -> right 포인터는 한번씩, left 포인터도 한번씩만 이동 

공간 복잡도 : O(1) -> 고정 배열 크기 26개(알파벳 대문자)만 사용 

class Solution {
    fun characterReplacement(s: String, k: Int): Int {
    
        // 슬라이딩 윈도우 + 문자 카운팅 
        val count = IntArray(26)
        var left = 0 
        var maxLen = 0
        var maxFreq = 0 
        for( right in s.indices) {
            val idx = s[right] - 'A'
            count[idx] ++ 
            maxFreq = max(maxFreq, count[idx])
            val windowSize = right-left +1 
            if(windowSize - maxFreq >k) {
                count[s[left] - 'A'] --
                left ++
            }
            maxLen = max(maxLen, right-left + 1)
        }
        return maxLen 
    }

 

3) minimum-window-substring

문제 : https://leetcode.com/problems/minimum-window-substring/

s, t 두개의 문자열이 주어졌을때, s가 t의 알파벳을 모두 포함할 수 있는 최소 문자열을 구하는 문제다. 

 

슬라이딩 윈도우 + 해시맵 비교를 통해서 해결할 수 있다. 

 

시간 복잡도 : O(n) -> 문자열 s의 left, right 포인터가 한번씩 이동(O(n)) + 맵에 데이터를 넣고 비교/ 카운트 하는 작업(O(1))

공간 복잡도 : O(1) -> s, t에 대한 카운트 저장 맵 2개, 가능한 문자열은 최대 128가지로 고정상수이므로 O(1) 

 

class Solution {
    fun minWindow(s: String, t: String): String {
        
        val tCount = mutableMapOf<Char, Int>()
        val windowCount = mutableMapOf<Char, Int>()
        for(c in t) {
            tCount[c] = tCount.getOrDefault(c, 0) +1
        }

        var left = 0 
        var have = 0 
        val need = tCount.size 
        var minLen = Int.MAX_VALUE
        var answer = ""
        for (right in s.indices) {
            val c = s[right]
            windowCount[c] = windowCount.getOrDefault(c, 0) + 1
            
            if(tCount.containsKey(c) && windowCount[c] == tCount[c]) {
                have ++
            }
            while(have == need) {
                if(right-left + 1<minLen) {
                    minLen = right - left + 1
                    answer = s.substring(left, right+1)
                }
                val leftChar = s[left]
                windowCount[leftChar] = windowCount[leftChar]!! -1
                if(tCount.containsKey(leftChar) && windowCount[leftChar]!! < tCount[leftChar]!!) {
                    have -- 
                }
                left ++ 
            }
        }
        return answer 

    }
}

 

 

 

4) Valid Anagram 

문제 : https://leetcode.com/problems/valid-anagram/

두개의 문자열이 주어지면 같은 알파벳으로 이루어져있는지 찾는 문제다.

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        val alpha = IntArray(26)

        for(char in s) {
            alpha[char-'a'] ++
        }

        for(char in t) {
            val idx = char-'a'
            alpha[idx] --
            if(alpha[idx]<0) {
                return false 
            } 
        }

        if(alpha.sum()>0) {
            return false 
        }
        return true 
    }
}

 

 

5) Group Anagrams 

문제 : https://leetcode.com/problems/group-anagrams/

여러개의 문자열이 주어지면, 같은 알파벳으로 이루어진 문자열들을 리스트로 묶어 반환하는 문제다. 

n = 문자열 개수, k = 각 문자열의 길이일때, 

sorted()를 사용하므로 시간 복잡도는 O(n * klogk)로 리스트가 길어질수록 병목이 될 수 있다 .

공간복잡도는 O(n*k) 다. (모든 문자열 저장 + 그룹화 저장) 

class Solution {
            fun groupAnagrams(strs: Array<String>): List<List<String>> {
                val map = mutableMapOf<String, MutableList<String>>()
                for(str in strs) {
                    val sorted = str.toCharArray().sorted().joinToString("") 
                    if(map.contains(sorted)) {
                        map[sorted]!!.add(str)
                    }else {
                        map[sorted] = mutableListOf(str)
                    }
                }
                val answer = mutableListOf<List<String>>()
                for(result in map.values) {
                    answer.add(result.toList())
                }
                return answer
            }
}

 

 

정렬을 사용하지 않고, 갯수 자체를 기록하는 방법을 사용하면 시간을 단축할 수 있다. 

시간 복잡도 = O(n*k) 

공간 복잡도 = O(n*k) 

class Solution {
    fun groupAnagrams(strs: Array<String>): List<List<String>> {
        val map = mutableMapOf<String, MutableList<String>>()

        for (str in strs) {
            val count = IntArray(26)
            for (c in str) {
                count[c - 'a']++
            }

            // 배열을 문자열로 변환 (ex: "1#0#0#..." 식으로 고유 키 생성)
            val key = count.joinToString("#")

            map.getOrPut(key) { mutableListOf() }.add(str)
        }

        return map.values.toList()
    }
}

 

 

6) Valid Parentheses 

문제 : https://leetcode.com/problems/valid-parentheses/

올바른 괄호 형식을 가지는지 찾는 전형적인 스택 문제다. 

class Solution {
    fun isValid(s: String): Boolean {
        if(s.length %2 != 0) {
            return false 
        }
        val input = listOf('(', '{', '[')
        val queue = Stack<Char>()
        for(char in s) {
            if(input.contains(char)) {
                queue.push(char)
            }else if(queue.isEmpty()){
                return false 
            }else {
                val pop = queue.pop() 
                if((pop == '(' && char != ')') || 
                    (pop == '{' && char != '}') ||
                    (pop == '[' && char != ']')
                ) {
                    return false 
                }
            }
        }
        if(queue.isNotEmpty()) {
            return false 
        }
        return true 
    }
}

 

 

맵을 활용하면 더 간결하게도 가능하다. 

class Solution {
    fun isValid(s: String): Boolean {
        val stack = Stack<Char>()
        val pairs = mapOf(')' to '(', '}' to '{', ']' to '[')

        for (char in s) {
            if (char in pairs.values) {
                stack.push(char)
            } else {
                if (stack.isEmpty() || stack.pop() != pairs[char]) return false
            }
        }

        return stack.isEmpty()
    }
}

 

 

Palindrome

 

1) valid-palindrome

문제 : https://leetcode.com/problems/valid-palindrome

주어진 문자열이 역순으로도 동일한 단어임을 구분한다. 

먼저 단순하게 최종 문자열을 구한뒤 역순으로 정렬한 값과 비교했다. 

시간복잡도 : O(n) 

공간복잡도 : O(n)

class Solution {
    fun isPalindrome(s: String): Boolean {
        var str = StringBuilder()
        for (c in s) {
            if(c.isLetterOrDigit()) {
                str.append(c.lowercaseChar())
            }
        }
        var result = str.toString()
        return result.reversed() == result
    }
}

 

 

미리 문자열을 모두 순회하지 않고, 투포인터 기법으로도 문제를 해결할 수 있다. 

 

시간복잡도 : O(1)

공간복잡도 : O(1)

class Solution {
    fun isPalindrome(s: String): Boolean {
        var left = 0 
        var right = s.length - 1
        while(left < right) {
            while(left < right && !s[left].isLetterOrDigit()) left++
            while(left < right && !s[right].isLetterOrDigit()) right--
            if(s[left].lowercaseChar() != s[right].lowercaseChar()) {
                return false
            }
            left++
            right--
        }
        return true 
    }
}

 

 

2) Longest Palindromic Substring 

문제 : https://leetcode.com/problems/longest-palindromic-substring/

 

문자열을 순회하면서 중심 지점을 선정하고 최대 길이를 가질 수 있는 문자열을 출력한다. 

시간복잡도 : O(n^2)

공간복잡도 : O(1)

class Solution {
    fun longestPalindrome(s: String): String {
        if(s.length < 2) return s

        var start = 0
        var end = 0 

        for(i in s.indices) {
            // 현재 시작점 i 
            val len1 = expand(s, i, i) // 홀수 개라고 가정하고 최댓값 계산 
            val len2 = expand(s, i, i+1) // 짝수 개라고 가정하고 최댓값 계산

            val len = maxOf(len1, len2)

            if(len>end-start) { // 최댓값 발생으로 정답 갱신 (홀수와 짝수에서 모두 정답을 낼 수 있는 인덱스 값 확인) 
                start = i - (len-1)/2 
                end = i + len/2
            }
        }
        return s.substring(start, end+1)
    }
    

    private fun expand(s:String, left:Int, right:Int): Int{
        var l = left 
        var r = right 

        while(l>=0 && r<s.length && s[l]==s[r]) {
            l--
            r++
        }

        return r-l-1
    }
}

 

 

3) palindromic-substrings

문제 : https://leetcode.com/problems/palindromic-substrings/submissions/1628517953/

palindromic의 갯수를 세는 문제로 상단의 문제를 응용해서 풀 수 있다. 

시간복잡도 : O(n^2)

공간복잡도 : O(1)

class Solution {
    fun countSubstrings(s: String): Int {
        var count = 0 

        for(i in s.indices) {
            count += expand(s, i, i)
            count += expand(s, i, i+1)
        }
        return count 
    }

    private fun expand(s: String, left: Int, right:Int): Int {
        var cnt = 0 
        var l = left 
        var r = right 
        while(l >=0 && r <s.length && s[l] == s[r]) {
            l--
            r++ 
            cnt++
        }
        return cnt 
    }

}

 

 

4) string-encode-and-decode

문제 : https://neetcode.io/problems/string-encode-and-decode

 

문자열을 encode하고 decode 하는 함수를 만든다. 

이때, 문자열을 누락하지 않고 그대로 encode, decode할 기준점을 잡아야 한다. 

 

class Solution {

    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for(int i =0; i < strs.size() ; i++) {
            sb.append(strs.get(i).length()).append("#").append(strs.get(i));
        }
        return sb.toString();
    }

    public List<String> decode(String str) {
        List<String> result = new ArrayList<String>();
        int i = 0 ;
        while(i < str.length()) {
            int j = str.indexOf('#', i); // i 부터 찾는다 
            int len = Integer.parseInt(str.substring(i, j)); // 문자열 사이즈 
            String s = str.substring(j+1, j+1 + len); // 문자열 
            result.add(s);
            i = j+1 + len ;
        }
        return result ;
    }
}