304 North Cardinal St.
Dorchester Center, MA 02124

# Biweekly Contest 69 LeetCode Solution

## Problem 1 – Capitalize the Title Leetcode Solution

You are given a string `title` consisting of one or more words separated by a single space, where each word consists of English letters. Capitalize the string by changing the capitalization of each word such that:

• If the length of the word is `1` or `2` letters, change all letters to lowercase.
• Otherwise, change the first letter to uppercase and the remaining letters to lowercase.

Return the capitalized `title`.

Example 1:

``````Input: title = "capiTalIze tHe titLe"
Output: "Capitalize The Title"
Explanation:
Since all the words have a length of at least 3, the first letter of each word is uppercase, and the remaining letters are lowercase.
``````

Example 2:

``````Input: title = "First leTTeR of EACH Word"
Output: "First Letter of Each Word"
Explanation:
The word "of" has length 2, so it is all lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.
``````

Example 3:

``````Input: title = "i lOve leetcode"
Output: "i Love Leetcode"
Explanation:
The word "i" has length 1, so it is lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.
``````

Constraints:

• `1 <= title.length <= 100`
• `title` consists of words separated by a single space without any leading or trailing spaces.
• Each word consists of uppercase and lowercase English letters and is non-empty.

### Capitalize the Title Leetcode Solution in C++

``````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;
}
``````

### Capitalize the Title Leetcode Solution in Java

``````class Solution {
public String capitalizeTitle(String title) {

char[] ch = title.toCharArray();
int len = ch.length;

for(int i = 0; i < len; ++i) {

int firstIndex = i; // store the first index of the word

while(i < len && ch[i] != ' ') {
ch[i] = Character.toLowerCase(ch[i]); // converting the character at ith index to lower case ony by one
++i;
}

// if word is of length greater than 2, then turn the first character of the word to upper case
if(i - firstIndex > 2) {
ch[firstIndex] =  Character.toUpperCase(ch[firstIndex]); // converting the first character of the word to upper case
}
}

return String.valueOf(ch); // return the final result by converting the char array into string
}
}
``````

### Capitalize the Title Leetcode Solution in Python

``````def capitalizeTitle(self, title: str) -> str:
return " ".join([word.lower() if len(word) < 3 else word.title() for word in title.split()])
``````

### Capitalize the Title Leetcode Solution in Python 3

``````    def capitalizeTitle(self, title: str) -> str:
ans = []
for s in title.split():
if len(s) < 3:
ans.append(s.lower())
else:
ans.append(s.capitalize())
return ' '.join(ans)
``````

## Problem 2 – Maximum Twin Sum of a Linked List Leetcode Solution

In a linked list of size `n`, where `n` is even, the `ith` node (0-indexed) of the linked list is known as the twin of the `(n-1-i)th` node, if `0 <= i <= (n / 2) - 1`.

• For example, if `n = 4`, then node `0` is the twin of node `3`, and node `1` is the twin of node `2`. These are the only nodes with twins for `n = 4`.

The twin sum is defined as the sum of a node and its twin.

Given the `head` of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

``````Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.
``````

Example 2:

``````Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.
``````

Example 3:

``````Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.
``````

Constraints:

• The number of nodes in the list is an even integer in the range `[2, 105]`.
• `1 <= Node.val <= 105`

### Maximum Twin Sum of a Linked List Leetcode Solution in C++

``````int pairSum(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
int maxVal = 0;

// Get middle of linked list
while(fast && fast -> next)
{
fast = fast -> next -> next;
slow = slow -> next;
}

// Reverse second part of linked list
ListNode *nextNode, *prev = NULL;
while (slow) {
nextNode = slow->next;
slow->next = prev;
prev = slow;
slow = nextNode;
}

// Get max sum of pairs
while(prev)
{
maxVal = max(maxVal, head -> val + prev -> val);
prev = prev -> next;
}

return maxVal;
}
``````

### Maximum Twin Sum of a Linked List Leetcode Solution in Python

``````def pairSum(self, head: Optional[ListNode]) -> int:
maxVal = 0

# Get middle of linked list
while fast and fast.next:
fast = fast.next.next
slow = slow.next

# Reverse second part of linked list
curr, prev = slow, None

while curr:
curr.next, prev, curr = prev, curr, curr.next

# Get max sum of pairs
while prev:
maxVal = max(maxVal, head.val + prev.val)
prev = prev.next

return maxVal
``````

### Maximum Twin Sum of a Linked List Leetcode Solution in Java

``````class Solution {
public int pairSum(ListNode head) {
ArrayList<Integer> al = new ArrayList<Integer>();
{
}
int i = 0;
int j = al.size()-1;
int sum = 0;
while(i < j)
{
sum = Math.max(al.get(i)+al.get(j), sum);
i++;
j--;
}
return sum;
}
}
``````

## Problem 3 – Longest Palindrome by Concatenating Two Letter Words Leetcode Solution

You are given an array of strings `words`. Each element of `words` consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from `words` and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return `0`.

palindrome is a string that reads the same forward and backward.

Example 1:

``````Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.
``````

Example 2:

``````Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.
``````

Example 3:

``````Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".
``````

Constraints:

• `1 <= words.length <= 105`
• `words[i].length == 2`
• `words[i]` consists of lowercase English letters.

### Longest Palindrome by Concatenating Two Letter Words Leetcode Solution in Java

``````    public int longestPalindrome(String[] words) {
Map<String, Integer> nonPaired = new HashMap<>();
int pairs = 0, sym = 0;
for (String w : words) {
String reverse = new StringBuilder(w).reverse().toString();
if (nonPaired.getOrDefault(reverse, 0) > 0) { // Find a counterpart for w among non-paired words.
++pairs;                                  // Increase the counter by 1.
nonPaired.merge(reverse, -1, Integer::sum); // Decrease reverse by 1 since it has been counted in pairs.
sym -= w.charAt(0) == w.charAt(1) ? 1 : 0; // Decrease sym by 1 since it has been counted in pairs.
}else {
nonPaired.merge(w, 1, Integer::sum); // Increase the occurrence of w.
sym += w.charAt(0) == w.charAt(1) ? 1 : 0; // Increase sym by 1.
}
}
return 4 * pairs + (sym > 0 ? 2 : 0);
}
``````

### Longest Palindrome by Concatenating Two Letter Words Leetcode Solution in Python 3

``````    def longestPalindrome(self, words: List[str]) -> int:
pairs, sym, nonPaired = 0, 0, Counter()
for w in words:
if nonPaired[w[:: -1]] > 0:
pairs += 1
nonPaired[w[:: -1]] -= 1
sym -= 1 if w == w else 0
else:
nonPaired[w] += 1
sym += 1 if w == w else 0
return pairs * 4 + (2 if sym > 0 else 0)
``````

### Longest Palindrome by Concatenating Two Letter Words Leetcode Solution in C++

``````class Solution {
public:
int longestPalindrome(vector<string>& words) {
int count=0;
//Create map and count all words frequency
map<string,int> m;
for(auto w:words) {
m[w]++;
}

//if single word like gg once done then not consider second time
//ex. cd*gg*dc
bool flag=false;
for(auto x:words) {
string w=x;
reverse(w.begin(),w.end());
//Encounter bc and cb then both freq -- by 1
if(w!=x and m[x]>0 and m[w]>0) {
m[x]--;
m[w]--;
count+=4;
} //Encounter aa and aa 2 times like bc*aa aa*cb,-- by 2 times
else if(w==x and m[x]>1) {
m[x]-=2;
count+=4;
} //Consider once like, bc*gg*cb
else if(w==x and !flag and m[x]>0) {
m[x]--;
count+=2;
flag=true;
}
}
return count;

}
};
``````

### Longest Palindrome by Concatenating Two Letter Words Leetcode Solution in Python

``````class Solution(object):
def longestPalindrome(self, words):
wc = collections.Counter(words)
aa = 0  # count how many words contain only two identical letters like 'aa'
center = 0  # if one count of 'aa' is odd, that means it can be the center of the palindrome, answer can plus 2
abba = 0 # count how many word pairs like ('ab', 'ba') and they can put on both sides respectively

for w, c in wc.items():
if w == w: # like 'aa', 'bb', ...
aa += c // 2 * 2 # if there are 3 'aa', we can only use 2 'aa' put on both sides respectively
# if one count of 'aa' is odd, that means it can be the center of the palindrome, answer can plus 2
if c % 2 == 1: center = 2
else:
abba += min(wc[w], wc[w[::-1]]) * 0.5  # will definitely double counting
return aa * 2 + int(abba) * 4 + center
``````

## Problem 4 – Stamping the Grid Leetcode Solution

You are given an `m x n` binary matrix `grid` where each cell is either `0` (empty) or `1` (occupied).

You are then given stamps of size `stampHeight x stampWidth`. We want to fit the stamps such that they follow the given restrictions and requirements:

1. Cover all the empty cells.
2. Do not cover any of the occupied cells.
3. We can put as many stamps as we want.
4. Stamps can overlap with each other.
5. Stamps are not allowed to be rotated.
6. Stamps must stay completely inside the grid.

Return `true` if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return `false`.

Example 1:

``````Input: grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
Output: true
Explanation: We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.``````

Example 2:

``````Input: grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2
Output: false
Explanation: There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.
``````

Constraints:

• `m == grid.length`
• `n == grid[r].length`
• `1 <= m, n <= 105`
• `1 <= m * n <= 2 * 105`
• `grid[r][c]` is either `0` or `1`.
• `1 <= stampHeight, stampWidth <= 105`

### Stamping the Grid Leetcode Solution in Java

``````    public boolean possibleToStamp(int[][] M, int h, int w) {
int m = M.length, n = M.length;
int[][] A = new int[m + 1][n + 1], B = new int[m + 1][n + 1], good = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + (1 - M[i][j]);
if (i + 1 >= h && j + 1 >= w) {
int x = i + 1 - h, y = j + 1 - w;
if (A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == w * h)
good[i][j]++;
}
}
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + good[i][j];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x = Math.min(i + h, m), y = Math.min(j + w, n);
if (M[i][j] == 0 && B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0)
return false;
}
}
return true;
}
``````

### Stamping the Grid Leetcode Solution in C++

``````    bool possibleToStamp(vector<vector<int>>& M, int h, int w) {
int m = M.size(), n = M.size();
vector<vector<int>> A(m + 1, vector<int>(n + 1)), B(m + 1, vector<int>(n + 1)), good(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + (1 - M[i][j]);
if (i + 1 >= h && j + 1 >= w) {
int x = i + 1 - h, y = j + 1 - w;
if (A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == w * h)
good[i][j]++;
}
}
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + good[i][j];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x = min(i + h, m), y = min(j + w, n);
if (M[i][j] == 0 && B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0)
return false;
}
}
return true;
}
``````

### Stamping the Grid Leetcode Solution in Python

``````    def possibleToStamp(self, M, h, w):
m, n = len(M), len(M)
A = [ * (n + 1) for _ in range(m + 1)]
good = [ * n for _ in range(m)]
for i in xrange(m):
for j in xrange(n):
A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + (1 - M[i][j])
if i + 1 >= h and j + 1 >= w:
x, y = i + 1 - h, j + 1 -w
if A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == w * h:
good[i][j] += 1
B = [ * (n + 1) for _ in range(m + 1)]
for i in xrange(m):
for j in xrange(n):
B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + good[i][j]
for i in xrange(m):
for j in xrange(n):
x, y = min(i + h, m), min(j + w, n)
if M[i][j] == 0 and B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0:
return False
return True
``````
##### Biweekly Contest 69 LeetCode Solution Review:

In our experience, we suggest you solve this Biweekly Contest 69 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Biweekly Contest 69 LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Biweekly Contest 69 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions