Palindromic Substring Queries | Dataford Interview Questions

Given a lowercase string (n up to 10^6) and queries [startIndex, endIndex, k], for each query output '1' if the substring can be made a palindrome by rearranging and at most k character substitutions, else '0'; return the result string.

Asked in the Online assessment stage. HackerRank OA, SDE II Connectors.

The relational input stores one character per row in string_characters and query ranges in palindrome_queries.

Output

Return one row with a result_string column.
Include one character, 1 or 0, per query in ascending query_id order.

Schema

string_characters

Column	Type	Description
positionPK	INT	One-based character position in the input string
character	VARCHAR(1)	Lowercase character at the position

palindrome_queries

Column	Type	Description
query_idPK	INT	Unique identifier defining output order
start_index	INT	Inclusive one-based substring start position
end_index	INT	Inclusive one-based substring end position
k	INT	Maximum allowed character substitutions

Your question is Palindromic Substring Queries. Start with the requirements and the two tables in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem