A. Capitalize the Title (opens new window)

DETAILS

string capitalizeTitle(string S) {
        for (int i = 0, j = 0; i <= S.size(); ++i) {
            if (i == S.size() || S[i] == ' ') {
                if (i > j + 2)
                    S[j] = toupper(S[j]);
                j = i + 1;
            } else {
                S[i] = tolower(S[i]);
            }
        }     
        return S;
    }

def capitalizeTitle(self, S: str) -> str:
        tmp = S.split(" ")
        ans = []
        for w in tmp:
            if len(w) < 3:
                ans.append(w.lower())
            else:
                ans.append(w[0].upper() + w[1:].lower())
        return " ".join(ans)

B. Maximum Twin Sum of a Linked List (opens new window)

Brute Force

DETAILS

int pairSum(ListNode* head) {
        vector<int> ans;
        while (head != nullptr) {
            ans.push_back(head->val);
            head = head->next;
        }
        int res = -1, n = ans.size();
        for (int i = 0; i < n/2; ++i) {
            res = max(res, ans[i] + ans[n - 1 - i]);
        }
        return res;
    }

public int pairSum(ListNode head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.val);
            head = head.next;
        }
        int n = ans.size(), res = -1;
        for (int i = 0; i < n/2; ++i)
            res = Math.max(res, ans.get(i) + ans.get(n - 1 - i));
        return res;
    }

def pairSum(self, head: Optional[ListNode]) -> int:
        ans = []
        while head:
            ans.append(head.val)
            head = head.next
        n = len(ans)
        return max(ans[i] + ans[n - 1 - i] for i in range(n//2))

Reverse Linked List

DETAILS

def pairSum(self, head: Optional[ListNode]) -> int:
        slow, fast = head, head
        ans = -1
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        cur = slow
        pre = None
        
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        while pre:
            ans = max(ans, head.val + pre.val)
            head = head.next
            pre = pre.next
            
        return ans

C. Longest Palindrome by Concatenating Two Letter Words (opens new window)

DETAILS

int longestPalindrome(vector<string>& W) {
        unordered_map<string, int> c;
        for (auto w : W) c[w]++;
        int ans = 0, mid = 0;
        for (auto &[key, val] : c) {
            auto rev = string(rbegin(key), rend(key));
            if (key == rev) {
                ans += 2 * (val / 2);
                if (val % 2 == 1) 
                    mid = 2;
            } else {
                auto p = c.find(rev);
                if (p != c.end())
                    ans += min(val, p->second);
            }
        }
        return 2 * ans + mid;     
    }

def longestPalindrome(self, W: List[str]) -> int:
        c = collections.Counter(W)
        ans, mid = 0, 0
        seen = set()
        for key in c:
            if key != key[::-1] and key not in seen and key[::-1] not in seen:
                ans += 4 * min(c[key], c.get(key[::-1], 0))
                seen.add(key)
            if key == key[::-1] and key not in seen:
                ans += 4 * (c[key] // 2)
                if c[key] % 2: mid = 2
                seen.add(key)
                
        return ans + mid

D. Stamping the Grid (opens new window)

DP

DETAILS

def possibleToStamp(self, A: List[List[int]], h: int, w: int) -> bool:
        m, n = len(A), len(A[0])       
        rsum = [[0] * (n + 1) for _ in range(m + 1)]
        inrange = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                rsum[i + 1][j + 1] = rsum[i][j + 1] + rsum[i + 1][j] - rsum[i][j] + (1 - A[i][j])      
                
        for i in range(h - 1, m):
            for j in range(w - 1, n):
                if rsum[i + 1][j + 1] - rsum[i + 1 - h][j + 1] - rsum[i + 1][j + 1 - w] + rsum[i + 1 - h][j + 1 - w] == w * h:
                    inrange[i][j] = 1
                
        B = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + inrange[i][j]
                
        for i in range(m):
            for j in range(n):
                x, y = min(i + h, m), min(j + w, n)
                if A[i][j] == 0 and B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0:
                    return False
        return True