Plaintiff-appellant Walter Friedl appeals from the January 13, 1999 order of the United States District Court for the Southern District of New York (John S. Martin, Jr., District Judge), granting defendants’ motion to dismiss Friedl’s action under 42 U.S.C. § 1983 and denying Friedl’s motion for leave to amend the complaint. We conclude that the district court erred by considering materials outside the pleadings in ruling on defendants’ motion to dismiss and that Friedl has stated a claim under section 1983. Accordingly, we vacate the judgment of the district court and remand for further proceedings. On remand, we direct the district court to allow plaintiff to amend his complaint.
BACKGROUND
The following facts are taken largely from plaintiffs complaint. Walter Friedl was convicted in 1982 for criminal possession of a forged instrument, but was not incarcerated until 1993, eleven years later, due to the misplacement of his conviction and commitment records by state and county officials. Ultimately, he was placed in the Queensboro Correctional Facility, which is operated by the New York State Department of Correctional Services (“DOCS”). Qn December 15, 1993, plaintiff was granted work release pursuant to *82New York State Correction Law, which allows inmates to “leavfe] the premises of an institution ... for the purpose of on-the-job training or employment.” N.Y. Correct. Law § 851(3) (McKinney 1999). Over time, Friedl was allowed to spend most nights at home, residing in prison only two nights each week.
On May 24, 1994, plaintiff applied to defendant New York City Human Resources Administration (“HRA”) for public assistance, food stamps, and Medicaid, disclosing his work release status and the fact that he was residing at home five nights a week. His application was denied on June 3, 1994, because he was “presently incarcerated and in [a] work release program” and thus allegedly “not eligible” for these benefits. Plaintiff requested and was granted a fair hearing with the New York State Department of Social Services (“DSS”) to appeal the HRA’s determination. On August 8, 1994, an administrative law judge (“ALJ”) ruled in favor of Friedl and instructed the HRA to “continue to process the Appellant’s application and afford the applicant the opportunity to submit any other documents necessary to establish eligibility.” The ALJ wrote:
The dispositive issue ... is not whether the Appellant is under supervision of the State of New York Department of Correctional Services, but whether the Appellant’s income and resources are sufficient or insufficient.... The Appellant’s credible testimony establishes that he is not incarcerated, nor residing in a public institution, that he lacks income and resources sufficient to meet his needs and that his needs are not being met. The denial of Appellant’s application ... is therefore improper.
Notwithstanding the ALJ’s ruling, on August 19, 1994, HRA once again denied Friedl’s application because he was “incarcerated and in a work release program” and thus “not eligible” for benefits.
According to the complaint, after the fair hearing decision was rendered, city defendant “Ms. Blackheath” (later identified as Ms. Blackett), an HRA supervisor, contacted Friedl’s parole officer, Pedro Torres, to inform him of plaintiffs application for benefits. Torres then charged plaintiff with “Inmate Misbehavior” under DOCS’s rules, alleging that Friedl had lied and attempted to commit welfare fraud. As a result, on August 25, 1994, Friedl appeared before the Queensboro Temporary Release Committee, which recommended his removal from the work release program, and the Queensboro superintendent, in turn, approved the recommendation. According to plaintiff, both the Committee and the superintendent refused to consider Friedl’s favorable ALJ ruling and “the absence of any restriction on applying for public assistance in the written rules and regulations governing his Work Release” in making their determination that he had engaged in misconduct. Friedl appealed his removal from work release, but before receiving the decision, he was approved for a second work release on or about November 15, 1994, approximately eighty days after his first work release was revoked. When the decision was ultimately issued, it concluded that the appeal was “Moot” because Friedl had been “re-approved for work release.”
On July 24, 1997, Friedl filed the instant action under 42 U.S.C. § 1983, naming as defendants both: (1) the City of New York and “Ms. Blackheath” (the “city defendants”); and (2) the members of the Queensboro Temporary Release Committee and the Queensboro superintendent (the “state defendants”). He claimed that the state defendants had violated his rights by “revoking his Work Release and reincarcerating him for welfare fraud when they knew from the administrative law judge’s decision ... that he had not committed welfare fraud and was merely exercising his federal rights to apply for benefits.” He alleged that these actions deprived him of liberty and property interests without due process of law, amounted to unlawful retaliation for his exercise of various constitutional and statutory rights, *83and infringed Ms First Amendment right to petition the government.
While discovery was proceeding, all defendants moved to dismiss the complaint pursuant to Fed.R.Civ.P. 12. Plaintiff then sought to amend his complaint to plead additional facts, identify various defendants individually rather than by occupational title, and add Officer Torres as a defendant. In reply papers, city defendants submitted, inter alia, excerpts from the deposition testimony of Blackett and Officer Torres. Plaintiff apparently objected to consideration of materials outside the pleadings.
On January 13, 1999, in an opinion that repeatedly indicated that Friedl’s application for benefits violated a condition of his work release, the district court dismissed the complaint in its entirety and denied plaintiffs motion to amend. See Friedl v. City of New York,, 1999 WL 11551 (S.D.N.Y. Jan.18, 1999). The court found that, although Friedl “likely had a liberty interest in ... continued participation in the work release program,” he “failed to allege how this liberty interest was deprived without due process of law” since he received notice, a hearing, and review of the Committee’s recommendation to revoke his release. Id. at *1. The district court also found no unlawful retaliation in the revocation of his work release since he had no constitutionally protected right under section 1983 to apply for public benefits. See id. at *2. Finally, the court found no violation of plaintiffs First Amendment right to petition the government because Friedl had failed to establish that the speech in his petition was a matter of public concern. See id. This appeal followed. Friedl later settled with the city defendants for $20,000 and withdrew the appeal as against them. Accordingly, we will confine our discussion to Friedl’s claims against the state defendants.
DISCUSSION
On appeal, we consider whether the district court erred in, first, dismissing plaintiffs complaint for failure to state a claim, and second, denying plaintiffs motion to amend his complaint.
I. Dismissal of the Complaint
We review de novo a district court’s decision to dismiss a complaint for failure to state a claim, taking all factual allegations in the complaint as true and construing all reasonable inferences in favor of the plaintiff. See Lee v. Bankers Trust Co., 166 F.3d 540, 543 (2d Cir.1999). Dismissal is “appropriate only if ‘it appears beyond doubt that the plaintiff can prove no set of facts in support of his claim which would entitle him to relief.’ ” Harris v. City of New York, 186 F.3d 243, 250 (2d Cir.1999) (quoting Conley v. Gibson, 355 U.S. 41, 45-46, 78 S.Ct. 99, 2 L.Ed.2d 80 (1957)). We conclude that the district court here erred in dismissing plaintiffs complaint against the state defendants because: (1) the court considered materials outside the pleadings in ruling on the motion to dismiss; and (2) the complaint states a claim under 42 U.S.C. § 1983.
A. Materials Outside the Pleadings
“[W]hen matters outside the pleadings are presented in response to a 12(b)(6) motion,” a district court must either “exclude the additional material and decide the motion on the complaint alone” or “convert the motion to one for summary judgment under Fed.R.Civ.P. 56 and afford all parties the opportunity to present supporting material.” Fonte v. Board of Managers of Continental Towers Condominium, 848 F.2d 24, 25 (2d Cir.1988). This conversion requirement is strictly enforced whenever there is a “legitimate possibility” that the district court relied on material outside the complaint in ruling on the motion. Amaker v. Weiner, 179 F.3d 48, 50 (2d Cir.1999). Thus, a district court errs when it “considers] affidavits and exhibits submitted by” defendants, Kopec v. Coughlin, 922 F.2d 152, 155 (2d Cir.1991), or relies on factual allegations contained in legal briefs or memoranda, see *84Fonte, 848 F.2d at 25, in ruling on a 12(b)(6) Motion to dismiss. Vacatur is required even where the court’s ruling simply “mak[es] a connection not established by the complaint alone” or contains an “unexplained reference” that “raises the possibility that it improperly relied on matters outside the pleading in granting the defendant’s Rule 12(b) motion.” Id.
Under these standards, vacatur is required here. In its ruling, the district court plainly relied on a matter outside the pleadings: specifically, defendants’ factual contention — contained in a declaration in support of their motion to dismiss and in opposition to plaintiffs motion to amend— that Friedl’s application for public benefits violated the conditions of his work release. See, e.g., Friedl, 1999 WL 11551, at *2 (“In this case, however, a condition of plaintiffs work release was that he work and not receive public assistance.”); id. (finding it “questionable” that “plaintiff had a right to apply for public assistance” “because it violated a condition of his work release”). The only reference to this matter in the pleadings was Friedl’s statement in his complaint that his work release should not have been revoked because, inter alia, there is no “restriction on applying for public assistance in the written rules and regulations governing his Work Release.” Although the district court explicitly found no due process violation even if plaintiff had a right to apply for benefits, see Friedl, 1999 WL 11551, at *2, we do not apply a “harmless error” analysis in this context. Moreover, we cannot be certain that the district court’s apparent conclusion that Friedl violated the conditions of his work release did not color its analysis of the merits of Friedl’s claims.
B. Section 1983 Claims
Plaintiff brought this action under 42 U.S.C. § 1983, claiming that the state defendants’ revocation of his work release following his application for public benefits violated his federally protected civil rights. Section 1983 provides, in relevant part:
Every person who, under color of any statute, ordinance, regulation, custom, or usage, of any State ..., subjects, or causes to be subjected, any citizen of the United States or other person within the jurisdiction thereof to the deprivation of any rights, privileges, or immunities secured by the Constitution and laws, shall be liable to the party injured in an action at law, suit in equity, or other proper proceeding for redress....
42 U.S.C. § 1983. Friedl articulates two claims under section 1983. First, he alleges that he was denied procedural due process when prison authorities withdrew him from the work release program. Second, he contends that his withdrawal from the program amounts to a substantive due process violation because his work release was revoked in retaliation for his application for, and appeal of the denial of, public benefits.
In our view, plaintiff has stated a claim for violation of his procedural due process rights. Prisoners on work release have a liberty interest in continued participation in such programs. See Kim v. Hurston, 182 F.3d 113, 117 (2d Cir.1999); Tracy v. Salamack, 572 F.2d 393, 395-96 (2d Cir.1978) (per curiam). The Due Process Clause protects inmates against “atypical and significant” deprivation of liberty, Sandin v. Conner, 515 U.S. 472, 484, 115 S.Ct. 2293, 132 L.Ed.2d 418 (1995), including withdrawal of work release. Thus, prisoners are entitled to procedural due process before they are subjected to such a deprivation of liberty.
Friedl’s complaint successfully alleged facts demonstrating that the procedures used to remove him were insufficient to satisfy minimum due process requirements. In the parole revocation context, the Supreme Court has held that due process requires:
(a) written notice of the claimed violations of parole; (b) disclosure to the parolee of evidence against him; (c) opportunity to be heard in person and to *85present .. evidence; (d) the right to confront and cross-examine adverse witnesses ...; (e) a "neutral and detached" hearing body such as a traditional parole board ...; and (f) a written statement by the factfinders as to the evidence relied on and reasons for revoking parole.
Morrissey v. Brewer, 408 U.S. 471, 489, 92 S.Ct. 2593, 33 L.Ed.2d 484 (1972). The Court has extended such protections to revocation of probation, see Gagnon v. Scarpelli, 411 U.S. 778, 782, 93 S.Ct. 1756, 36 L.Ed.2d 656 (1973), "good time credits," see Wolff V. McDonnell, 418 U.S. 539, 558, 94 S.Ct. 2963, 41 L.Ed.2d 935 (1974), and pre-parole release, see Young v. Harper, 520 U.S. 143, 152-53, 117 S.Ct. 1148, 137 L.Ed.2d 270 (1997), and similar requirements would logically apply to revocation of work release. In addition, the Court has specifically held that "revocation of good time credits does not comport with the `minimum requirements of procedural due process' unless the findings of the prison disciplinary board are supported by some evidence in the record." Snperin-tendent, Mass. Correctional Inst. v. Hill, 472 U.S. 445, 454, 105 S.Ct. 2768, 86 L.Ed.2d 356 (1985); see Zavaro v. Coughlin, 970 F.2d 1148, 1153 (2d Cir.1992) (holding that hearing officer violated inmate's due process rights by finding him guilty of misconduct where hearing "record failed to meet the `some evidence' standard established by the Supreme Court in Hill ").
Here, Friedl received notice and a hearing before the Committee, an opportunity to present evidence on his own behalf, and the right to appeal the decision to remove him. However, he alleges that the state nonetheless denied him due process by "finding him guilty of misconduct without any evidence to support the charges" (emphasis added). Under Hill, the minimum requirements of due process are met only if "there was some evidence from which the conclusion of the administrative tribunal could be deduced." Hill, 472 U.S. at 454, 105 S.Ct. 2768. Accordingly, Friedl's allegation that the Committee's revocation of his work release was unsupported by even a modicum of evidence suffices to state a claim under 42 U.S.C. § 1983. Of course, if during the course of discovery it emerges that there is any evidence in the record that supports the Committee's finding, Hill mandates that summary judgment be granted in defendants' favor and plaintiffs procedural due process claim be dismissed. Our conclusion here is based solely on plaintiffs allegation that there was no evidence to support finding him guilty of misconduct.
In addition, we find as a matter of law that plaintiff has stated a claim for retaliation based on his exercise of constitutionally and statutorily protected rights. In general, a section 1983 claim will lie where the government takes negative action against an individual because of his exercise of rights guaranteed by the Constitution or federal laws. See Hynes v. Squillace, 143 F.3d 653, 657 (2d Cir.1998) (per curiam) (citing Mt. Healthy Sch. Dist. v. Doyle, 429 U.S. 274, 287, 97 S.Ct. 568, 50 L.Ed.2d 471 (1977)); Greenwich Citizens Comm., Inc. v. Counties of Warren & Washington Indus. Dev. Agency, 77 F.3d 26, 33 (2d Cir.1996) (suggesting that plaintiffs may state "claims of alleged retaliation for the exercise of a constitutional or statutory right" under 42 U.S.C. § 1983) (emphasis added). We have confirmed that this principle applies in the prison context as well. See Colon v. Coughlin, 58 F.3d 865, 872 (2d Cir.1995) (holding that prisoners have a right to petition for redress of grievances and that prison officials may not retaliate against prisoners who exercise this right). In order to state a claim for retaliation under section 1983, a plaintiff must show that: (1) his actions were protected by the Constitution or federal law; and (2) "the defendant's conduct complained of was in response to that protected activity." Posr v. Court Officer Shield # 207, 180 F.3d 409, 418 (2d Cir.1999). To survive a mo*86tion to dismiss, such claims must be “supported by specific and detailed factual allegations,” not stated “in wholly conclusory terms.” Flaherty v. Coughlin, 713 F.2d 10, 13 (2d Cir.1983). However, a plaintiff need not show that the retaliatory action was taken without basic procedural guarantees, since the retaliation is itself a substantive due process violation. See Franco v. Kelly, 854 F.2d 584, 589 (2d Cir.1988).
Under these standards, Friedl has stated a section 1983 claim for retaliation. First, we are satisfied that his conduct was protected both by statute and by the Constitution. Assuming the terms of his work release did not provide otherwise, Friedl had a statutory right to apply for, and appeal the denial of, at least some public benefits, even if he were later determined to be ineligible due to his status as prisoner or for any other reason. See, e.g., 42 U.S.C. § 1396a(a)(8) (requiring states to “provide that all individuals wishing to make application for medical assistance under [Medicaid] shall have opportunity to do so” and to furnish “such assistance ... to all eligible individuals”) (emphasis added); id. § 1396a(a)(3) (requiring states to grant a fair hearing to “any individual whose claim for medical assistance ... is denied”) (emphasis added).
In addition, the administrative adjudication of Friedl’s asserted right to receive public assistance benefits while on work release was constitutionally protected. Plaintiff had a First Amendment right to petition the government for redress of grievances, see Franco, 854 F.2d at 588-89; Haymes v. Montanye, 547 F.2d 188, 191 (2d Cir.1976)—here, to appeal the denial of public benefits. As we have stated:
[T]he right to petition government for redress of grievances [i]s among the most precious of the liberties safeguarded by the Bill of Rights. Moreover, the right of petition applies with equal force to a person’s right to seek redress from all branches of government. In the prison context, ... inmates must be permitted free and uninhibited access to both administrative and judicial forums for the purpose of seeking redress of grievances against state officers.... [I]ntentional obstruction of a prisoner’s right to seek redress of grievances is precisely the sort of oppression that section 1983 is intended to remedy.
Franco, 854 F.2d at 589 (internal quotation marks and citations omitted).
The Supreme Court more recently has found that the fundamental constitutional right of access to the courts
does not guarantee inmates the wherewithal to transform themselves into litigating engines capable of filing everything from shareholder derivative actions to slip-and-fall claims. The tools it requires to be provided are those that the inmates need in order to attack their sentences, directly or collaterally, and in order to challenge the conditions of their confinement. Impairment of any other litigating capacity is simply one of the incidental (and perfectly constitutional) consequences of conviction and incarceration.
Lewis v. Casey, 518 U.S. 343, 355, 116 S.Ct. 2174, 135 L.Ed.2d 606 (1996). Sitting in banc, a sharply divided Sixth Circuit recently interpreted Lewis to mean that “a prisoner’s right to access the courts extends to direct appeals, habeas corpus applications, and civil rights claims only.” Thaddeus-X v. Blatter, 175 F.3d 378, 391 (6th Cir.1999) (in banc).
However, these pronouncements do not alter our conclusion that Friedl’s adjudication was constitutionally protected. Nothing in Lewis forecloses an administrative challenge by a prisoner to the conditions of his confinement, and we decline to follow the restrictive interpretation placed on Lewis by the Sixth Circuit in Thaddeus-X, since not every “challenge to the conditions of confinement” takes the form of a civil rights action. In particular, Friedl’s administrative adjudication, though it involved no civil rights claim, plainly impli*87cated the conditions of his confinement: he wanted to discover whether, as a result of his status as a participant in the work release program, he was entitled to public assistance benefits.
Furthermore, we reject the contention, accepted by the district court, that where the plaintiff alleges retaliation for protected speech in the form of a petition to the government, he must "establish that the speech contained in his petition to the government was a matter of public concern." Friedl, 1999 WL 11551, at *2 (citing White Plains Towing Corp. v. Patterson, 991 F.2d 1049, 1058 (2d Cir.1993)). The "public concern" requirement, developed in the context of public employee speech, has no place in the context of prisoner petitions for redress of grievances, which typically address matters of personal concern. See Thaddeus-X, 175 F.3d at 392. Cf. Graham v. Henderson, 89 F.3d 75, 77 (2d Cir.1996) (allowing a section 1983 claim to go forward where a prisoner claimed retaliation based on his petitions regarding the elimination of showers in the prison workshop). In sum, we conclude that Friedl's conduct in pursuing public assistance benefits was both statutorily and constitutionally protected.
Second, Friedl explicitly and sufficiently alleges that prison officials revoked his work release in retaliation for this protected conduct. According to the complaint, there is a clear causal chain: Friedl appealed the denial of benefits; the AU reversed this denial; an HRA worker informed Friedl's parole officer of his application for benefits; the officer charged Friedl with inmate misbehavior; Friedl was brought before the Temporary Release Committee; the Committee recommended revocation of his work release; ultimately, within ten days of the date the parole officer was informed of Friedl's application for public benefits, his work release was withdrawn. These allegations of retaliation are not conclusory; they are sufficiently specific to state a claim.
It may well be that the state defendants can defend this action for retaliation by successfully establishing a right under the terms of the work release program to remove Friedl from the program when he applied for public benefits. The parties strongly dispute whether work release was explicitly conditioned on not applying for benefits. This issue is more appropriately resolved after discovery, either on a motion for summary judgment or at trial.
II. Denial of Motion to Amend
On August 14, 1998, plaintiff moved to amend his complaint based on information acquired during depositions and other discovery. First, he wanted to drop the New York City Department of Human Services as a defendant, identify some current defendants by name (specifically, Blackett, the members of the Temporary Release Committee, and the Deputy Superintendent of the prison), and add Officer Torres as a defendant. Second, he sought to plead additional facts, including alleged actions by and communications between Blackett and Officer Torres aimed at undermining Friedl's application for public benefits and punishing him for applying.
After responsive pleadings have been filed, subsequent amendments are possible only with leave of court, but such leave "shall be freely given when justice so requires." Fed.R.Civ.P. 15(a). In general, district courts should not deny leave unless there is a substantial reason to do so, such as excessive delay, prejudice to the opposing party, or futility. See Jones v. N.Y. Div. of Military & Naval Affairs, 166 F.3d 45, 50 (2d Cir.1999) (futility); MacDraw, Inc. v. CIT Group Equip. Fin., Inc., 157 F.3d 956, 962 (2d Cir.1998) (per curl am ) (delay or prejudice). We review a district court's denial of a motion to amend for abuse of discretion; but where the "court based its denial ... on a conclusion of law [,] . . . that conclusion of law is subject to review de novo." Sheldon v. PHH Corp., 135 F.3d 848, 851-52 (2d Cir.1998).
*88The district court here denied plaintiffs motion to amend his complaint “[b]ecause plaintiff has failed to state a cause of action for any of his claims.” Friedl, 1999 WL 11551, at *3. However, as discussed above, plaintiffs complaint does state a claim under 42 U.S.C. § 1983; thus, the district court’s disposition was based on an error of law. Moreover, there has been no showing of either undue delay, given that the amendment was proposed only after discovery revealed additional relevant facts, or prejudice to the defendants, given the minimal extent of the proposed changes. Accordingly, on remand, we instruct the district court to grant plaintiff leave to amend his complaint.
CONCLUSION
For the foregoing reasons, we conclude that the district court erred in dismissing plaintiffs complaint against the state defendants because: (1) the court considered materials outside the pleadings in ruling on the motion to dismiss; and (2) the complaint states a claim under section 1983. We also find that the district court should have permitted Friedl to amend his complaint. Accordingly, we vacate the judgment of the district court and remand for further proceedings consistent with these determinations. The costs of this appeal shall be taxed against the appellees.