Make Every Password Block a Palindrome
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Implement `minimum_palindromic_block_changes(password, k)`.
The password length is a multiple of `k`. Partition it into consecutive blocks of exactly `k` characters. You may replace any character with any lowercase English letter. Return the minimum number of replacements needed so that every block is a palindrome.
### Constraints
- `1 <= len(password) <= 200000`
- `1 <= k <= len(password)` and `len(password) % k == 0`
- `password` contains only lowercase English letters.
### Examples
- `"abcaabba"`, `k = 4` returns `1`: change the first block `abca` to a palindrome; `abba` already is one.
- `"abcdef"`, `k = 3` returns `2`: each of `abc` and `def` needs one mirrored-pair change.
- `"aaaa"`, `k = 1` returns `0`.
```hint Exercise both parity cases
Test odd and even block lengths, including `k = 1` and an already-palindromic block.
```
```hint Check edits at different locations
Include blocks whose disagreements occur near the ends, near the center, and in more than one place.
```
Overview: Implement `minimum_palindromic_block_changes(password, k)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Partition `password` into consecutive blocks of exactly `k` characters. You may replace any character with any lowercase English letter. Return the minimum number of replacements needed so that every block is a palindrome. The password length is always a multiple of `k`.
Constraints
- 1 <= len(password) <= 200000.
- 1 <= k <= len(password), and len(password) is a multiple of k.
- password contains only lowercase English letters.
Examples
Input: ('a', 1)
Expected Output: 0
Explanation: A one-character block is already a palindrome.
Input: ('aaaa', 1)
Expected Output: 0
Explanation: Every length-one block needs zero replacements.
Hints
- Test both odd and even block lengths, including k = 1 and an entire-password block.
- Include already-palindromic blocks and blocks with disagreements near the ends and near the center.
- Use several consecutive blocks so zero-, one-, and multiple-change blocks contribute to one total.
Community answers
Answer by testingprachub
def minimum_palindromic_block_changes(password, k):
# TODO
i = 0
ans = 0
def minCharacters(substr:str)->int:
l=0
r = len(substr)-1
minchars = 0
while l<r:
if substr[l] != substr[r]:
minchars += 1
l+=1
r-=1
return minchars
while i < len(password):
ans += minCharacters(password[i:i+k])
i+=k
return ans