Appearance
question:You are given a string of length N consisting of only lower case alphabetical letters. Your task is to determine if the string can be rearranged such that no two adjacent characters are the same. If such a rearrangement is possible, print "YES"; otherwise, print "NO". INPUT The first line contains a single integer N, the length of the string. The second line contains the string of length N consisting of only lower case alphabetical letters. OUTPUT Print "YES" if the string can be rearranged such that no two adjacent characters are the same. Otherwise, print "NO". CONSTRAINTS 1 ≤ N ≤ 100000 SAMPLE INPUT 5 aabbc SAMPLE OUTPUT YES Explanation One possible rearranged string is "abcab", where no two adjacent characters are the same. Therefore, the output is "YES".
answer:def can_rearrange_string(N, s): Determine if the string can be rearranged such that no two adjacent characters are the same. Parameters: N (int): length of the string s (str): string consisting of only lower case alphabetical letters Returns: str: "YES" if the string can be rearranged, "NO" otherwise from collections import Counter freq = Counter(s) max_freq = max(freq.values()) # no of remaining characters remaining = N - max_freq if max_freq - 1 > remaining: return "NO" else: return "YES"
question:Given a directed graph with N vertices and M edges. Your task is to identify whether there exists at least one cycle in the graph. Each edge is represented as a pair of integers (u, v) meaning there is a directed edge from vertex u to vertex v. The vertices are numbered from 1 to N. Example 1: Input: N = 3, M = 3 Edges = [[1, 2], [2, 3], [3, 1]] Output: Yes Explanation: The graph has a cycle: 1 -> 2 -> 3 -> 1. Example 2: Input: N = 4, M = 4 Edges = [[1, 2], [2, 3], [3, 4], [4, 2]] Output: Yes Explanation: The graph has a cycle: 2 -> 3 -> 4 -> 2. Example 3: Input: N = 3, M = 2 Edges = [[1, 2], [2, 3]] Output: No Explanation: The graph has no cycle. Your Task: Your task is to complete the function `hasCycle()` which takes the number of vertices N, the number of edges M, and a list of edges as inputs and returns a string "Yes" if the graph contains at least one cycle, otherwise it returns "No". Expected Time Complexity: O(N + M) Expected Auxiliary Space: O(N) Constraints: 1 <= N, M <= 10^5 1 <= u, v <= N
answer:def hasCycle(N, M, Edges): from collections import defaultdict, deque # Create adjacency list for the graph graph = defaultdict(list) for u, v in Edges: graph[u].append(v) # Helper function to check cycle from a node using DFS def isCyclic(v, visited, recStack): # Mark the current node as visited and set it in the recursion stack visited[v] = True recStack[v] = True # Recur for all neighbours for neighbour in graph[v]: if not visited[neighbour]: if isCyclic(neighbour, visited, recStack): return True elif recStack[neighbour]: return True # Remove the vertex from recursion stack recStack[v] = False return False # Mark all the vertices as not visited and not part of recursion stack visited = [False] * (N + 1) recStack = [False] * (N + 1) # Call the helper function to detect cycle in different DFS trees for node in range(1, N + 1): if not visited[node]: if isCyclic(node, visited, recStack): return "Yes" return "No"
question:A college brings you a new task! They provide you with a string consisting of only lowercase letters. You have to determine and print the maximum length of a substring in which no character repeats more than once. -----Input----- A single line contains a string s (1 ≤ |s| ≤ 10^5), which consists of only lowercase English letters. -----Output----- Print a single integer — the maximum length of a substring with all distinct characters. -----Examples----- Input: abcabcbb Output: 3 Input: bbbbb Output: 1 Input: pwwkew Output: 3
answer:def length_of_longest_substring(s): Returns the length of the longest substring with all distinct characters. n = len(s) ans = 0 char_index = {} i = 0 # Start of the current substring for j in range(n): if s[j] in char_index: i = max(char_index[s[j]], i) ans = max(ans, j - i + 1) char_index[s[j]] = j + 1 return ans
question:In a peaceful village, the villagers decide to organize a lantern festival on a long straight road. They will light up n lanterns along the road. The positions of the lanterns are given, and the road is symmetrical. Each lantern i provides a light range from position (i-d) to position (i+d). The aim is to ensure that the entire road from position 0 to position L is illuminated by the lanterns. Determine the minimum light radius d that all lanterns should have to cover the entire road. Input The first line contains two integers n and L (1 ≤ n ≤ 1000, 1 ≤ L ≤ 10^9). The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ L; all ai are unique and sorted in ascending order). Output Output the minimum light radius d that ensures all positions on the road from 0 to L inclusive are illuminated by the lanterns. Examples Input 3 10 2 5 8 Output 2 Input 2 5 0 5 Output 2.5 Input 4 15 1 5 11 13 Output 3 Note In the first sample: - Light radius d = 2 ensures that lantern positions (2-2) to (2+2), (5-2) to (5+2), and (8-2) to (8+2) cover the entire road 0 to 10. In the second sample: - Light radius d = 2.5 ensures that lantern positions (0-2.5) to (0+2.5) cover [0, 5], and lantern positions (5-2.5) to (5+2.5) cover [0, 5]. In the third sample: - Light radius d = 3 lights up positions 1, 5, 11, and 13 sufficiently to cover the entire road from 0 to 15.
answer:def min_light_radius(n, L, positions): Returns the minimum light radius d that ensures all positions on the road from 0 to L inclusive are illuminated by the lanterns. # Calculate the maximum gap between consecutive lanterns max_gap = max(positions[0], L - positions[-1]) for i in range(1, len(positions)): max_gap = max(max_gap, (positions[i] - positions[i - 1]) / 2) return max_gap