Problem Description

This take-home project consists of two independent algorithmic challenges. You are required to provide an optimal solution for each part, including the algorithm description, its time complexity, and space complexity.

Part 1: Transform to Palindromic K-Periodic String

Given a lowercase string currentPassword and an integer k, your task is to transform currentPassword into a newPassword that satisfies two conditions:

1. newPassword is a palindrome.
2. newPassword is k-periodic, meaning newPassword[i] = newPassword[i + k] for all valid indices i (0-based).

You may change any character in currentPassword to any other lowercase letter. The cost of this operation is 1 for each character changed. Your goal is to find the minimum number of character changes required.

Constraints:

• 1 <= k < len(currentPassword) <= 2 * 10^5
• len(currentPassword) is divisible by k.

Example:

• currentPassword = "abzzbz", k = 3
• One optimal newPassword is "zbzzbz".
• The minimum number of character changes required is 1.

Part 2: Minimize Processing Cost with Daily Discount

You are given n images, each with an associated filterCost, startDay, and endDay. For any given day d, the set of active images includes all images i such that startDay[i] <= d <= endDay[i].

Without a discount, the processing cost for day d is the sum of filterCost[i] for all active images i on that day. You have the option to apply a discount at most once per day. If the discount is applied on day d, the total cost for that day becomes exactly discountPrice, regardless of the sum of active image filter costs.

Your objective is to process all n images over their required day ranges, minimizing the total cost across all days. Return this minimum total cost modulo 1,000,000,007.

Input:

• n: integer, the number of images.
• filterCost: an array of n integers, where filterCost[i] is the cost for image i.
• startDay: an array of n integers, where startDay[i] is the first day image i is active.
• endDay: an array of n integers, where endDay[i] is the last day image i is active.
• discountPrice: an integer, the cost when a discount is applied.

Example:

• n = 3
• filterCost = [2, 3, 4]
• startDay = [1, 1, 2]
• endDay = [2, 3, 4]
• discountPrice = 6

Calculations for example:

• Day 1: Active images: {1, 2} (since startDay[1]=1 <= 1 <= endDay[1]=2 and startDay[2]=1 <= 1 <= endDay[2]=3). Cost without discount = filterCost[1] + filterCost[2] = 2 + 3 = 5.
• Day 2: Active images: {1, 2, 3} (since startDay[1]=1 <= 2 <= endDay[1]=2, startDay[2]=1 <= 2 <= endDay[2]=3, startDay[3]=2 <= 2 <= endDay[3]=4). Cost without discount = filterCost[1] + filterCost[2] + filterCost[3] = 2 + 3 + 4 = 9.
• Day 3: Active images: {2, 3} (since startDay[2]=1 <= 3 <= endDay[2]=3, startDay[3]=2 <= 3 <= endDay[3]=4). Cost without discount = filterCost[2] + filterCost[3] = 3 + 4 = 7.
• Day 4: Active images: {3} (since startDay[3]=2 <= 4 <= endDay[3]=4). Cost without discount = filterCost[3] = 4.

Optimal Strategy for example:

• Apply discount on Day 2 (cost 9 -> 6).
• Apply discount on Day 3 (cost 7 -> 6).
• Total cost = 5 (Day 1) + 6 (Day 2 discounted) + 6 (Day 3 discounted) + 4 (Day 4) = 21.